Cryptography-Digest Digest #483, Volume #11 Tue, 4 Apr 00 05:13:02 EDT
Contents:
Re: Magnetic Remenance on hard drives. ("dlk")
Cipher Contest (Boris Kazak)
Re: Cipher Contest (Boris Kazak)
Re: Cipher Contest (Boris Kazak)
Re: Cipher Contest (Boris Kazak)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (DMc)
Passwords in Zip Archives (Patrick Bangert)
Re: Q: Entropy (Mok-Kong Shen)
----------------------------------------------------------------------------
From: "dlk" <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,alt.security.pgp
Subject: Re: Magnetic Remenance on hard drives.
Date: Tue, 04 Apr 2000 07:57:04 GMT
The only problem with software solutions for this problem is the small but
definite probability that it didn't work. If the data is truly that
sensitive, nothing
beats physical destruction: incineration and/or crushing the platters.
Hard to read anything from a glob o' slag: A 'gas-ax' (oxy-acetylene
torch) works wonders. Particularly if it has a cutting tip: heat 'em till
they're cherry red then shoot the O2 to 'em - poof! platter & data are
so much vapor.
However, for drives that have given one some trouble in the past or
contain software that one just loathes, you get some nice satisfaction from
driving a cold chisel thru the !@#$ repeatedly with a hefty hammer...
(just be sure and wear safety glasses: pieces-parts go everywhere!)
Dave Keever
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Cipher Contest
Date: Tue, 04 Apr 2000 08:20:15 GMT
Hey sci.crypters,
I have taken a look at the first submission to the cipher list. Mr.
Kazak
submitted the cipher Letsief.
<http://www.wizard.net/~echo/crypto-contest.ht>
The cipher is a feistel network that combines modular multiplication, a
secret
s-box, and XOR. The security of the cipher rests in the secrecy of the
s-box
and the secrecy of the sub keys. The sub keys are XOR in with half the
data.
The right half is hashed in and the result is used to select one entry
from the
secret sbox. The sbox entry is then multiplied by the left half. The
halves
are switch and the next round starts.
The hash which is used to select the sbox entry is a simple XOR of the
bytes of
the right side.
The s-box consists of 256 32-bit values. The values are chosen in a
pseudo
random fashion but the space is only 2^16. So the sbox is 256 values
from 65536
possible values, quite small.
The strength of the cipher appears to rely on the non-linear
relationship
between XOR and modular multiplication.
In general, (a*b)^(c*b) != (a^c)*b so the distributive property seems
to be the
strength.
Combining the above, an attacker can get a look inside the s-box.
In the last round, the hash of the right side will give the entry that
is used
in the sbox. Using XOR as the notation of difference, we can find two
ciphertexts that hash too the same value. We then know that the left
side is
multiplied by the same number and then XOR with a whitening key.
K is the whitening key. M is the sbox multiplier. u and v are unknown
input
from the previous round.
L1 = (u*M)^K
L2 =(v*M)^K
L1^L2 = (u*M)^(v*M)
The above equation can serve to distinguish between values in the
s-box. Not
all values can satisfy the equation if L1^L2 is a known value. By
assuming M to
be one of the possible 2^16 values and trying several pairs practically
all of
the values can be eliminated. Note also, that not all of the bits need
be used,
sometimes the few right most bits are adequate to discard a value. I
used brute
force to evaluate the equation but mostly likely there are much more
efficient
ways.
By following the above procedure all of the 256 values in the s-box can
be
narrowed to just a few values.
It appears to be possible to run the key schedule backwards if the ss
array is
known. The above procedure will reveal a large chunk of the array
thereby
weakening the cipher dangerously.
For fun, lets assume the key schedule is one-way. We then have a
version of
Letsief with a known s-box and secret round keys. This version appears
to be
vulnerable to differential analysis.
In the last round the output of the s-box is known for ciphertexts. If
we can
cause a differential of (0,x) in the previous round then we have the
equation.
M and M1 are a known multipliers.
L1 = (u*M)^K
L2 = (u*M1)^K
L1^L2 = (u*M)^(u*M1)
By brute force we can identify possible u candidates. Once u is known
the K can
be deduced. Once K is known then a round can be peeled off the cipher.
The differential is controlled by the hash of the right sides. A random
collision will occur in once in 2^8 for a specific value. We start the
differentials as (x,0) when the notion of difference is XOR and the x
value is
the hash of interest. For eight rounds, one good pair will occur in
2^32 pairs.
By running the differential for many pairs, one value of K will occur
more than
others.
A sixteen round version would requite 2^64 ciphertext,, quite alot.
Oddly this
cipher allows for 2^128-2^8 == 2^120 pairs do to nature of the s-box
selection.
Letsief is a fun and interesting cipher but does not appear to be
'strong'.
--Matthew
--
NOTICE: The information contained in this electronic mail transmission
is
intended by Convergys Corporation for the use of the named individual or
entity
to which it is directed and may contain information that is privileged
or
otherwise confidential. If you have received this electronic mail
transmission
in error, please delete it from your system without copying or
forwarding it,
and notify the sender of the error by reply email or by telephone
(collect), so
that the sender's address records can be corrected.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Cipher Contest
Date: Tue, 04 Apr 2000 08:24:37 GMT
At suggestion of Mr. Fisher I am transferring all this
discussion to the group.
Matthew Fisher wrote:
> I have taken a look at the first submission to the cipher
> list. Mr. Kazak submitted the cipher Letsief.
******
> ... an attacker can get a look inside the s-box.
> In the last round, the hash of the right side will give
> the entry that is used in the sbox. Using XOR as the
> notation of difference, we can find two ciphertexts that
> hash to the same value. We then know that the left side is
> multiplied by the same number and then XOR with a whitening key.
===================
A note for those who will read this post:
Mr. Fisher means here any attack where the attacker has
enough ciphertext to look for pairs matching in the hash of
their right halves. So if the pair is R1-L1 and R2-L2,
it is assumed that R1 and R2 hash to the same 8-bit value.
This really assures that the same modular multiplier was
used in both cases; M = Mult[8-bit hash]. Mult[] is the
table of modular multipliers with 128 pairs of entries,
multiplier and its inverse occupy adjacent cells.
Returning now to Nr. Fisher's presentation...
=================================================
> K is the whitening key. M is the sbox multiplier.
> u and v are unknown input from the previous round.
> L1 = (u*M)^K
> L2 =(v*M)^K
> L1^L2 = (u*M)^(v*M)
> The above equation can serve to distinguish between values
> in the s-box. Not all values can satisfy the equation
> if L1^L2 is a known value. By assuming M to be one of the
> possible 2^16 values and trying several pairs practically
> all of the values can be eliminated.
================================================
Now that's more like wishful thinking...
The "above equation" has 3 unknowns - u, v and M.
The only things that are known about M with any degree of
certainty are that M has a multiplicative inverse, that this
inverse occupies the adjacent cell in the Mult[] array, and
that M and (2^32-1) are relatively prime.
It is easy to show that, in case of modular multiplication
(mod 2^32-1) thus chosen M defines a bijective transformation
of 32-bit values.
Now, following Mr. Fisher's notation, let us denote
DIFF = L1^L2 = (u*M)^(v*M) Difference between pairs
MI = M^(-1) multiplicative inverse of M
and write an obvious relation.
For any u there exists a v such that
v = ((u*M)^DIFF)*MI
and since this is true for any M, so Mr. Fisher's attack does
not work against LETSIEF. (Not any single one of 2^16 possible
multipliers can be eliminated).
==========================================================
**********************
> It appears to be possible to run the key schedule backwards
> if the ss array is known. The above procedure will reveal
> a large chunk of the array thereby weakening the cipher
> dangerously.
======================================
It seems that Mr. Fisher has taken a look inside the program
code, so I can encourage him even more. The ss[] array
IS THE KEY, or more precisely, the direct offspring of the
key. If you know the ss[] array, you know everything -
the first 48 bytes produce 12 round keys for whitening,
next 256 bytes produce the powers to raise the SEED when
you stuff the MULT[] array with multipliers and inverses.
If you know the ss[] array, it just makes sense to run
the key schedule forward, stuff the P and S boxes and
to launch the cipher in Decryption Mode...
This is why key[], ss[], P[] and Mult[] must be kept
secret. BTW, nobody doubts the requirement of secrecy
for BLOWFISH's P and S boxes.
=============================================
> For fun, lets assume the key schedule is one-way.
> We then have a version of Letsief with a known s-box and
> secret round keys. This version appears to be
> vulnerable to differential analysis.
> **************
> M and M1 are a known multipliers.
>
> L1 = (u*M)^K
> L2 = (u*M1)^K
> L1^L2 = (u*M)^(u*M1)
=============================================
Very instructive, but v-v-e-ery far from reality.
All the point of the elaborate key schedule is to
stuff the Mult[] array with randomized multipliers.
If the multipliers will be *known*, the cipher can
be placed in a coffin and brought to the cemetery.
=============================================
> For eight rounds, one good pair will occur in 2^32 pairs.
> By running the differential for many pairs, one value
> of K will occur more than others.
>
> A sixteen round version would requite 2^64 ciphertext,
> quite alot. Oddly this cipher allows for
> 2^128-2^8 == 2^120 pairs do to nature of the s-box selection.
=============================================
Thank you for analysis, Matthew, may be you will
reconsider your final conclusion?
Best wishes Boris Kazak
=============================================
> Letsief is a fun and interesting cipher but does not
> appear to be 'strong'.
>
> --Matthew
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Cipher Contest
Date: Tue, 04 Apr 2000 08:28:54 GMT
From:
<[EMAIL PROTECTED]>
Gentlemen,
Do you think we should move the discussion to sci.crypt? I had
visualized the
cipher contest as basis for cryptanalysis discussion. The more the
better in
these sorts of discussion. I hope that some professional cryptographer
might
take an interest as well.
I have my own cipher to submit. I am polishing the code and will have
it
together by the end of the week.
Back to Letsief, I have developed a differential attack. I believe the
attack
breaks the cipher but I have been wrong before:-) I don't believe the
attack is
practical however. The search time will be around 2^83 or so.
To avoid embarassing myself again, I wrote a small program to find the
differentials. I have included it at the bottom.
The differential attack:
Hold the right side steady with both values chosing the index in the
Mult array
e.g. (0x1 ^ 0x100) = 0x101. The chosen value will be 1 for both of the
elements
in the differential in this example.
Let the left side vary but keep it equal for both pairs e.g . (0x12343 ^
0x12343) = 0x00000.
Keep checking pairs until a left side differential of 0 is found i.e.
find a
pair where the output left side is equal.
The right side value of such a pair will usually be not equal.
Such a differential will occur when the Mult selection value collides in
each
round. The probability of such a differential is 2^-(8*((R-2)/2)). 8
rounds
is 2^-24, so about one in 16000000 pairs hits.
Let the right side XOR = B. Here is a four round differential
Left Right
0 B probabilty of a clash = 1 because B is
chosen
B1 0 p = 1 since the selectors are equal
0 B2 p = 1/(2^8), a lucky hit is needed
B3 0 p = 1
0 B4 left side = (L0^L1) = 0, right side (R0^R1) =
any
value
Let S(), denote the xor of all bytes in a word. If the differential
holds
S(R0) = S(R1) for the round before last (1)
and
(R0*M) ^ (R1*M) = B4 (2)
S(L0) = S(L1) equal the selector for the last round
I don't believe the above two equations hold for every possible value.
We can
therefore sieve based on S(L0). We know of Mult[S(L0)] is one of 2^16
values.
By gathering several pairs, and then evaluating 2^56 numbers for
equations (1)
and (2), the candidates can be thinned. By gathering enought pairs,
only one
values should remain. By repeating this step for each of the 128
entries the
s-box can be revealed.
The above differential is quite similar to the weak key Blowfish
differential.
If multiple entries in the s-box are equivalent the probability of the
differential will decrease.
The following program will find differentials but does not do the
sieving step.
I experimented with 16-bit number sieving and found good results.
Hopefully, I
have the math right on that part.
/* the program need LETSIEF.c as well */
void main()
{
union {
word32 All[2] ;
byte Byte[8] ;
} P, P1 ;
word32 i,j,k;
strcpy(key,"matthew");
Lets_init(7);
for(k=1;k<pow(2,30);k++)
{
P.All[0] = k;
P1.All[0] = k;
P.All[1] = 0x45; /* the index into the Mult array */
P1.All[1] = 0x45 << 8; /* by shifting we get a new value but the
same byte
XOR */
Lets_block_encrypt (P.Byte);
Lets_block_encrypt (P1.Byte);
if(P.All[0] == P1.All[0])
{
printf("%03d %03d %03d\n",k,
P.Byte[4] ^ P.Byte[5] ^ P.Byte[6] ^P.Byte[7],
P1.Byte[4] ^ P1.Byte[5] ^ P1.Byte[6] ^P1.Byte[7]);
}
}
}
cheers,
--Matthew
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Cipher Contest
Date: Tue, 04 Apr 2000 08:34:28 GMT
Agreed, discussion is being transferred to sci.crypt.
I take the liberty to post there all 4 of these messages, to
arrange them into a thread, and to name this thread so that
it would be easy to follow the trail.
Now about the substance - proposed differential attack.
First of all, I am a little confused about the direction
of the attack. Do we introduce the differences in the
plaintext before encryption and then try to trace their
propagation along the encryption path,
or do we encrypt some random plaintext in search for
specific differences appearing in the ciphertext?
Quoting the original message:
> Let the right side XOR = B. Here is a four round differential
> Left Right
> 0 B probabilty of a clash = 1 because B is chosen
> B1 0 p = 1 since the selectors are equal
> 0 B2 p = 1/(2^8), a lucky hit is needed
> B3 0 p = 1
> 0 B4 left side = (L0^L1) = 0,
> right side (R0^R1) = any value
it is not clear, which way does the procedure go - from
1-st round forward or from last round backward. However,
in any case, the behavior of differences seems to be
misinterpreted.
Case 1 - forward.
In this case apparently the difference between the right
halves is chosen so that the hashes of the 2 right sides are
the same, and the same multiplier is applied to left halves
in both cases. Left halves are supposed to be identical.
This means that in both cases after the first round left
halves will remain identical, and the multiplier selected
before the second round will be the same (although different
from the previous one).
Here, obviously, the goodies end - the second multiplier
will be applied to different right halves, and there is no
realistic way of predicting the values of the resulting
right half products - modular multiplication does not care
about XOR differences and does not preserve those, especially
with randomly chosen multipliers.
The previous table must look this way:
(B, B2, B3, B4 - differences)
Rd L0^L1 R0^R1
0 0 B probabilty of a clash = 1 because B is chosen
1 0 B p = 1 since the selectors are equal
2 0 B2 B2 can be any value
3 B3 B2 B3 and B2 can be any value
4 B3 B4 left side = (L0^L1) = any value,
right side (R0^R1) = any value
Case 2 - backward.
In this case apparently the difference between the right
halves is chosen so that the hashes of the 2 right sides are
the same, and the same multiplier was applied to left halves
in both cases. Left halves are supposed to be identical.
This means that in both cases before the last round left
halves were indeed identical, and the multiplier selected
for the round before the last was the same (although different
from the last one).
Here, obviously, the goodies end - the second multiplier
was applied to different right halves, and there is no
realistic way of predicting the values of the preceding
right halves - in the previous post it was shown that any
multiplier can produce the necessary difference between the
products, if original values were suitable. It was also shown
that no multiplier can be eliminated this way.
The previous table must look this way:
(B, B2, B3, B4 - differences)
Rd L0^L1 R0^R1
8 0 B probabilty of a clash = 1 because B is chosen
7 0 B p = 1 since the selectors were equal
6 0 B2 B2 could be any value
5 B3 B2 B3 and B2 could be any value
4 B3 B4 left side = (L0^L1) = any value,
right side (R0^R1) = any value
The overall conclusion is that it is impossible to trace the
differences beyond 1.5 rounds from eiter side. Intermediate
whitening between the rounds also helps to cut short the
possibility for difference tracing.
Even in the most pessimistic case if we shall admit that
3 rounds can(??) be "peeled" off LETSIEF, the remaining
5 rounds introduce 5x16bit uncertainty in multipliers alone,
even disregarding 5x32bit whitening round keys.
Mr. Fisher's estimate of 2^83 work for breaking the cipher
via differential attack seems close to reality, but one
should remember in this case that for this cipher there are
only 2^64 possible plaintexts... Sic!
Again my sincere thanks to Mr Fisher for analysis.
Best wishes BNK
------------------------------
From: DMc <[EMAIL PROTECTED]>
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: Tue, 04 Apr 2000 08:45:34 GMT
On Mon, 03 Apr 2000 23:09:46 -0700, Anthony Stephen Szopa
<[EMAIL PROTECTED]> wrote:
[snip]
>You certainly realize that there is at least one person in this news group
>that actually thinks that the random digits from the random digit
>generator are used directly in the encryption process. This is because
>he hasn't a clue.
>There may even be some in this news group that think that the random
>numbers from 000 - 255 calculated directly from the random number
>generator are used directly in the encryption process. These people
>also haven't a clue.
I may be that one person, or at least one of those persons. Except,
I took you at your original word that your downloadable "pseudorandom"
generator was NOT to be used for crypto purposes.
>For any who need a lesson: first a random digit triplet is formed directly
>from the random digit generator.
I fully understand this is your intended procedure. Currently, I am
not able to do that procedure. Your "lessons" have a great many words
about what you are doing, and how great that is for all of us, but
very little about how to do it in a reasonable fashion.
>If this number is greater than 767 it is discarded. Otherwise this number
>is divided by 3 and the remainder is truncated. This and all subsequent
>random numbers from 000 - 255 calculated in this manner are then
>stored in RandOut files usually having a length of 18144000 binary
>bytes each. [snip]
This is where you and I presently part company. I am only interested
how random your "random numbers from 000 - 255" are. So far, after
reading an enormous number of words from you, I only have your
assurance they are "true random" numbers.
If "true random" numbers, then it is possible for your final crypto
product to be what you say it is. If not, I suggest the old saying of
"making a silk purse out of sow's ear" is relevant.
By the way, it is your burden to define, and explain what you mean
by, "true random" numbers.
>These several RandOut files are further processed repeatedly using
>as many as ten different processes. All processes use true random
>user input as parameters.
[snip]
>Let's now discuss your proposition strictly regarding the random digit
>generator (this is not a discussion about the OAP-L3 software as a
>whole.)
Exactly what I want to do. It is you who keeps shifting the subject
beyond this point. (See your 4th comment below.)
>First let me say this: everyone knows that computer software
>programs are entirely deterministic.
So far, there are only conjectures about that. I know that some
mathematicians have presented complexity and finite space theories,
but none currently raise above mere conjecture.
>Knowing the algorithm and the inputs you can predict the output
>before even running the process if you are so inclined.
Fascinating bull hockey; Take the simple Park and Miller minimal
standard generator with an initial seed of 1. Now tell me the 1 073
741 825th seed value without running the generator.
>You can also go the other way.
Double, maybe quadruple, bull hockey!
>Regarding encryption software I like to think of there being an
>explicit key and an implicit key.
[snip]
See, here you are talking crypto use again. Maybe you, like William
Jefferson Clinton, have a unique definition of "strictly regarding."
>I do agree that you can at least show your employer that you have
>done something in the hopes of justifying your salary but
>unfortunately you have gotten no further to the goal of cracking
>the OAP-L3 software.
I get that you are attempting to sell your crypto system to some
group of people. Do you honestly think you are going to do well with
that goal by insulting people?
[EMAIL PROTECTED]
------------------------------
From: Patrick Bangert <[EMAIL PROTECTED]>
Subject: Passwords in Zip Archives
Date: Tue, 04 Apr 2000 09:53:06 +0100
Dear All,
I recently created zip archives with some important work of mine for
backup purposes. I need to unzip these now since I need the backup but I
have forgotten the password I put on them. Is there some kind of a
utility that will allow me to find the password? (This is not for
illegal use - it is truly for my own files!)
Thanks.
Pat
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Tue, 04 Apr 2000 11:09:51 +0200
Joseph Ashwood wrote:
> > A further question: Does a normal English message have
> entropy?
> Yes, it typically has between 1 and 2 bits of entropy per
> character, depending on who wrote it. It is quite easy to
> establish that there must be some entropy, otherwise
> different texts could not be written, establishing the
> actual amount is quite difficult and includes computing the
> odds of statements of a given length, and determining from
> that the entropy of that length, then comparing several of
> those lengths to create an estimate.
My point is that the difficulty lies in quantifying (as against
qualifying) entropy in actual practice. This conforms to what
you said. To exaggerate a bit, entropy seems like beauty. Most
people would agree that some of the famous stars are prettier
than an average woman, but it is hard to say by just how much or
to compare two of the stars. Under such conditions, I suppose
that the question could be legitimately asked whether arguments
in practical situations employing entropy, say, whether a password
has more entropy than another or how much entropy one has
collected through certain means, shouldn't be considered to be
essentially fuzzy and at least looked upon with one or several
grains of salt.
> > Presumably yes. Now if I change some words but retain the
> > grammatical structures, does the new (artificial) message
> (that
> > is not quite common) have a larger/smaller entropy? Or is
> it rather
> > the case that one has no exact methodology to deal with
> that issue?
> If there is a 1 to 1 relationship between your new language
> and it's corresponding English version the entropy of the
> new language message will be the same as the entropy of the
> english version, if the translation is more complex it would
> take more analysis to estimate the entropy. However the
> language occurance would make for higher entropy of language
> choice, for example, if it is known that I speak only
> English (and it's slang variants), there is little inherent
> entropy in my language choice. OTOH if I speak All variant
> of english, chinese (yes all however many variants),
> spanish, french, italian, hindi, COBOL, C, x86 assembly,
> etc, etc etc. it becomes more difficult to determine the
> language I will be speaking, making for some apparent
> entropy that is not actually present in my speech.
There is no new language. I remain in the domain of English. In
such situations I am not sure of the entropy remaining the same.
For I could exchange some nouns or verbs such that the new sentence
does not have any sense in the real world, even though it remains
to be correct grammatically. (For instance, one substitutes 'cat'
for 'computer', 'eat' for 'invent' etc.) In that case the
probability of that sentence occuring in the language (as ensemble
of sentences formulated by people) would be much smaller than the
original, I believe.
M. K. Shen
=========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
