Cryptography-Digest Digest #916, Volume #10 Mon, 17 Jan 00 01:13:01 EST
Contents:
Re: Cracking DES (JPeschel)
Re: New Crypto Regulations (JPeschel)
Re: Cracking DES (Bill Unruh)
Re: My Encryption system (Scott Contini)
R.A.T.2 (Jeff Lockwood)
Re: My Encryption system ("Scott Fluhrer")
R.A.T.2 - error in the decode function (Jeff Lockwood)
Re: NTRU Cryptosystems Inc. (David Wagner)
Re: Ciphers for Parallel Computers (David Wagner)
Re: NTRU Cryptosystems Inc. (David Wagner)
Re: NTRU Cryptosystems Inc. (David A Molnar)
RNG for OTPs during WWII ("Bayard Randel")
Re: "1:1 adaptive huffman compression" doesn't work (Peter Rabbit)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Cracking DES
Date: 17 Jan 2000 01:10:18 GMT
[EMAIL PROTECTED] (Paul Schlyter) writes:
>In article <[EMAIL PROTECTED]>,
>JPeschel <[EMAIL PROTECTED]> wrote:
>
>> [EMAIL PROTECTED] (Paul Schlyter) writes:
>>
>>> The only known way to crack single DES is by brute force: if you have
>>> one cleartext-cryptotext pair, try all possible keys until you
>>> encounter the correct key.
>>
>> It's not always necessary for an attacker to possess one cleartext-
>> cryptotext pair.
>
>OK, but then you must have some other way to determine whether
>you've obtained the correct cleartext or not.
>
Of course.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: New Crypto Regulations
Date: 17 Jan 2000 01:42:33 GMT
"John E. Kuslich" [EMAIL PROTECTED] writes, with a mischevious smile on his face,
in part:
>And as for you...Why the heck the Virgin Islands? How in the heck can
>they stay virgin for so long. Sounds like a pretty stern place for a
>vacation?
Gee, it's a bit warmer there in winter than it is in South Dakota.
I guess I won't be sending you a USVI tee-shirt! :-)
>You...you DEMOCRAT! :-)
Yup, that's me: a capital DEMOCRAT!
>That's all, I promise. I have had my little rant. Now back to cracking
>passwords.
Okeedokee, guess I'll get back to doing the same, and will try to figure
out a way to keep this tan without flying down to Phoenix.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Cracking DES
Date: 17 Jan 2000 01:59:03 GMT
In <85rbaj$ll1$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>Maybe a silly question:
>How do we know what the right key is by non-cleartext-cryptotext?
>If we think a right key has been found, maybe there is another
>possible key with another possible solution.
Higly unlikely. The key is only 56 bits long. The chances of say ascii
text being produced for 8 bytes is approximately 1/3^8 (ie only 1/3 or
all 8 bit bytes are printable ascii.) Or if it is text much less (
estimates for English are that each latter is onle about 1.5 bits of
entropy, so that would be more like 1/6^8. Thus two or three blocks
would make the chance much less that 1/2^56. Ie, you find a key which
gives reasonable output for th first block . There will be many. But for
the key to also give reasonable output on the second black as well it is
much closer. By the time you get to three or four blocks, the chances
are overwhelming that you have the right key. This of course assumes
that the cleartext actually has clear patterns (like it is ascii text,
etc) If not, the job is more difficult. Eg, if DES encrypted text which
was really text encrypted by some other completely unknown cypher, then
you could not brute force the DES ( since the plaintext would be
entirely random and would not be identifiable as the correct
plaintext).
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: My Encryption system
Date: 17 Jan 2000 02:01:33 GMT
In article <[EMAIL PROTECTED]>,
D10n... [o] <[EMAIL PROTECTED]> wrote:
>This is a multi-part message in MIME format.
>--------------088A507DC86BF4C936BFF151
>Content-Type: text/plain; charset=us-ascii
>Content-Transfer-Encoding: 7bit
>
><snip all>
>R.A.T. encryption is quite good. It's inovative. When I saw that the base
>functions were XOR's I felt sure it would be easy to crack but I was mistaken.
>There is not enough information to reverse engineer the ciphertext. Also,
>identical letters are not encrypted the same 99.9% of the time. Those few times
>when an individual letter is encrypted that same as a previous occurance makes
>things just that little bit harder.
>
>The encryption and decryption routines are small and fast and there is a nice
>sized key. As previously stated, this system may be open to brute force attacks.
>Given the size of the key this would involve some great time with a normal home
>computer but perhaps tens of hours with a super computer.
or if you use your brain, you can get a typical PC to crack it in
minutes. Read my post about the cryptanalysis. Every 256 bytes
of ciphertext will leak one byte of the key, on average. This is
a VERY, VERY poor property for a cipher to have. And I might also
add that I only spent 1 hour looking at it - further analysis would
probably find many more weaknesses.
------------------------------
From: Jeff Lockwood <[EMAIL PROTECTED]>
Subject: R.A.T.2
Date: Mon, 17 Jan 2000 11:48:50 +1100
I hope this version fixes the problems in my previous effort. Thankyou
for the replys I have recieved so far.
Description of my R.A.T.2 encoding and decoding method
Notes:
all values and variables mentioned in this document will be single byte
quantities , with values ranging from 0-255.
the key is an array of 256 bytes; containing all all the possible values,
sorted into a random order, with one extra requirement: the value contained
in each cell of the array cannot be the same as the index number of the cell
eg: cell 0 cannot contain 0, cell 1 cannot contain 1 ,...
Before encoding, fill array k2 with the locations of each byte in the key array.
eg: k2[0] is the location of 0 in the key array, k[1] is the location of 1 in the key
array.
Variables:
K This is the 256 byte key array
K2 this is the 256 byte index to the key array
X This contains the data byte to be encoded
A This is used as an index into the key array
B This is used as an index into the key array, and for
the encoded output byte.
A1 This is used for temporary storage
B1 This is used for temporary storage
The Encode function:
1) Initialise variable A with the value 0 and B with 128.
2) read 1 byte into X.
3) The value in X is XORed with the byte in k[B],
and the result is stored in A1.
4) The value in A1 is XORed with byte in k[A],
and the result replaces the value stored in B.
5) Write out the the byte in k2[B]
6) Replace the value in A with the value in A1
7) Loop back to step 2 until all bytes have been encoded.
The Decode function:
1) Initialise variable A with the value 0 and B with 128.
2) read 1 byte into B1.
3) The value in k[B1] is XORed with the byte in k[A],
and the result replaces the value in A.
4) The value in A is XORed with the byte in k[B],
and the result is stored in X.
5) write out the value in X
6) replace the value in B with the value in B1.
7) loop back to step 2 until all bytes have been decoded.
Aditional notes:
Thankyou to the people in the sci.crypt news group, for showing me where
I went wrong in my earlier version.
The above functions are released into the public domain. You may use them
in any program (even commercial ones). they may also implemented directly
in hardware. I place no restrictions upon their use.
I also release this document into the public domain and permit distribution
without any restrictions.
Jeff Lockwood January 17 2000
[EMAIL PROTECTED]
Jeff Lockwood <[EMAIL PROTECTED]>
PGP public key:
homepages.ihug.com.au/~satan/pgpkey.asc
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: My Encryption system
Date: Sun, 16 Jan 2000 18:13:56 -0000
Jeff Lockwood <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> It seems , that exposing a value that is used as one of the indexes in the
> next iteration was not a good idea at all.
>
> The Fix:
>
> create another array of 256 bytes; where each location containes an
> index into the key array. call it K-index;
>
> eg:
> k-index[0] contains the location of 0 in the key,
> k-index[1] contains the location of 1 in the key;
>
>
> Now , instead of outputting B , I'll output k-index[B] .
>
> in the decode routine, X will now become key[X].
>
>
> That ought to do it.
I see that you still haven't bothered writing out your encryption in formal
(read: mathematical) notation. Hint: to be taken at all seriously, you
really need to do this. Lets see if we can do this for (this is the last
time, mind):
You new method appears to retain ( X(...) is the plaintext, Y(...) is
the ciphertext, and A(...) and B(...) are internal variables:
A(n+1) = X(n) ^ key[ B(n) ]
B(n+1) = X(n) ^ key[ A(n) ] ^ key[ B(n) ]
and makes the output be:
Y(n+1) = key^-1[ B(n+1) ] where key^-1 is the inverse of key
or,
key[ Y(n+1) ] = B(n+1)
Here's how a simple extension of my previous attack works against
this new method. Just like last time, algebra gives us
B(n+2) = X(n+1) ^ key[ B(n+1) ] ^ key[ X(n) ^ key[ B(n) ] ]
Note that, because key[...] is a permutation, then if Y(n)=Y(m), then
B(n)=B(m). Then, if we look for indicies n, m such that:
X(n) = X(m) Y(n) = Y(m) Y(n+1) = Y(m+1) Y(n+2) != Y(m+2)
then, algebra gives us:
B(n+2) ^ B(m+2) = X(n+1) ^ X(m+1)
or,
key[ Y(n+2) ] ^ key[ Y(m+2) ] = X(n+1) ^ X(m+1)
Again, this gives us the XOR of two elements of key. Find enough
of these, and the uncertainly in key should drop to a point where
brute force is possible. Back-of-the-envelope calculations imply
that, for random plaintext, a few tens of k of known
plaintext/ciphertext should suffice.
Now, Mr. Wagner recommended that you shouldn't bother tweaking
your scheme against specific known attacks -- I suggest you
follow his advice. He knows what he's talking about. Personally,
I think you should work on your cryptanalytic skills. One place
to start would be http://www.counterpane.com/self-study.html.
If you don't know how to break a bad cipher, how can you ever
expect to make a good one?
--
poncho
------------------------------
From: Jeff Lockwood <[EMAIL PROTECTED]>
Subject: R.A.T.2 - error in the decode function
Date: Mon, 17 Jan 2000 12:06:28 +1100
in step 6 of the decode funcion, it says,
replace the value in B with the value in B1,
it should say,
replace the value in B with the value in k[B1].
sorry,
Jeff Lockwood <[EMAIL PROTECTED]>
PGP public key:
homepages.ihug.com.au/~satan/pgpkey.asc
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NTRU Cryptosystems Inc.
Date: 16 Jan 2000 20:08:29 -0800
In article <85tp8l$465$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
> It's probably better just to ignore all the text and go straight to the
> conference papers.
Yes, I've read several of them, and the one I saw were fascinating and
generally very well written. My complaint is, of course, not with the
technical work, but rather with NTRU's marketing department.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Ciphers for Parallel Computers
Date: 16 Jan 2000 20:13:19 -0800
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> [...] which is a set of 4 simple equations in GF(2)^4, but so far as I
> know there is no general methodology for solving such systems that
> takes appreciably less work than a brute-force search over the domain
> (for larger systems, anyway).
You might enjoy reading Kipnis and Shamir's CRYPTO'99 paper, which
describes an extraordinarily clever technique (`relinearization') for
solving roughly this class of problems, if I recall correctly.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NTRU Cryptosystems Inc.
Date: 16 Jan 2000 20:16:52 -0800
In article <[EMAIL PROTECTED]>,
lordcow77 <[EMAIL PROTECTED]> wrote:
> RSA with low exponents may not be equivalent to factoring.
RSA with large exponents may not be, either. And so it goes....
> That notwithstanding, I believe the 100x figure refers to generation
> of public/private key pairs.
Ahh, that would explain it. Thanks for pointing out that possibility!
Of course, if this is what they intended, my complaint still stands
-- the way they state this claim is highly deceptive, IMHO, and when
trust is your business, deception is a perhaps imprudent marketing
policy. But I could see where it could have came from, anyway.
Then again, maybe I'm just a crusty curmudgeon to nitpick on this point. :-)
> It can be programmed from scratch in perhaps 3 or
> 4 hours, depending on how rusty one is at programming the algorithm for
> finding the inverse of a polynomial.
Neat!
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: NTRU Cryptosystems Inc.
Date: 17 Jan 2000 04:33:41 GMT
David Wagner <[EMAIL PROTECTED]> wrote:
> Yes, I've read several of them, and the one I saw were fascinating and
> generally very well written. My complaint is, of course, not with the
> technical work, but rather with NTRU's marketing department.
Amen. I guess this brings up the question of what good marketing would
look like. How do you make marketing claims about crypto
which are
a) faithful to the technical results (i.e. not misleading)
b) address customer interests
and
c) not so general to be vacuous, not so specific as to be irrelevant ?
d) any other criteria I've overlooked
In particular, how do you compare the "speed" of two public-key systems?
Use a specific implementation, and your comparison is obsolete in a few
months. Simply count exponentiations and other primitive operations, and
then it's no longer immediate which is better, and by how much (especially
if comparing different types of operations). So should we take a model
like the one at cryptosavvy.com, pick a bar, and then see what the
parameters for the new system are? then where do space and randomness
consumption requirements fit in?
Thanks,
-David
------------------------------
From: "Bayard Randel" <[EMAIL PROTECTED]>
Subject: RNG for OTPs during WWII
Date: Mon, 17 Jan 2000 18:08:42 +1300
Just out of historic interest, would anyone happen to know what sort of RNGs
would have typically been used by either Allied or Axis forces for OTP
keystream generation ? dice, playing cards ?
Bayard Randel
Christchurch, NZ
------------------------------
From: Peter Rabbit <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Date: Mon, 17 Jan 2000 06:08:23 GMT
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> :> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> :> :> : Tell me in what sense the software is not portable?
> :> :>
> :> :> If you have no convenient source of genuine randomness, it won't work.
> :> :> Not every system comes with a good hardware source of random numbers.
> :> :> If you use something []at all [p]redictable, you introduce possible
> :> :> problems.
> :>
> :> : I don't understand what 'possible problems' you would have.
> :>
> :> The attacker knows something about the data in the compressed file,
> :> information which he need not be supplied with. He knows it is likely
> :> to have certain non-random stuff at its end. This is less than ideal.
>
> : Are you going to argue like those who unconditionally want 'absolute'
> : security?
>
> Clearly there's no such thing.
>
> : Note that one never gets 100.00% pure gold in this world,
> : there is always some foreign atoms in there. Returning to the present
> : case, we are discussing about the (practical) problem raised by Scott.
> : Do you think that my proposed scheme has 'practically' solved the
> : problem or not?
>
> In practice, the Huffman ending problem appears to offer the attacker few
> footholds anyway. Seven bits per message may compromise some systems,
> but not very many. At worst it knocks this number of bits off the
> keyspace. Most systems should withstand this, most of the time.
>
> I don't know if your scheme reduces the problem to acceptable levels.
> What is "acceptable" depends on your application.
>
> I see your scheme as an source of unnecessary and easily eliminated
> potential weakness. I don't see what the problem is with using the ideal
> Huffman file ending scheme, now that it has been discovered.
>
> : How does one proceed to exploit the 'certain non-random stuff'?
>
> I've given in some detail one way the analyst might get information from
> this, even if the padding is /totally/ random.
>
> Giving the analyst unnecessary information about plaintext statistics in
> messages is not a good idea. I'm sure you can figure out what an analyst
> can do with such information for yourself.
>
> : Please tell me a 'concrete' way to get some 'information' out of
> : these that is 'actually' sensible to his task, namely to decrypt
> : to obtain the information in the bit sequences 'preceeding'
> : these 2 filling bits.
>
> If he has one message, his job is not easy. Also, your question
> is not necessarily the right one. With two bits of information, he's
> not going to get /much/ useful information about the rest of the message -
> unless the message has a two bit key.
>
> I've explained how /even/ totally random padding can give the analyst
> information he wouln't haveif a deterministic compressor had been used,
> that might help identify the sender.
>
> I'm uncertain why I face yet more questions along the same lines.
>
> Haven't I made my point already?
>
> :> : In fact, I don't need 'true randomness', nor even
> :> : 'pseudo-randomness', only 'non-constancy'.
> :>
> :> This won't do at all, IMO.
>
> : Please explain.
>
> You think (say) preferentially padding with zeros is generally acceptable
> behaviour, despite the fact that it gives away probably-known plaintext?
>
> Would you more more concerned if you were padding to a 128-bit block
> rather than an 8-bit one?
>
> : Don't just put up a claim without any supporting material [...]
>
> I was under the impression that giving away probable plaintext to
> attackers was generally considered undesirable. I'm a bit puzzled
> about being asked for "supporting material". The attacker gains
> statistical knowledge about the plaintext, which was previously
> unavailable to him. What more do I need to say?
>
> You want me to spell out how to analyse frequency information in
> messages, when statistical characteristics of the plaintext are
> known?
>
> I'll give an example, which should demonstrate how an analyst might be
> helped.
>
> He has a bunch of messages, which he knows from the context of
> their interception contain encyphered-compressed password data.
>
> The passwords were generated by a random number generator.
>
> Each password is encyphered with its own key.
>
> The analyst wants access to the passwords.
>
> [In this instance compression doesn't help, but the compressor was built
> into the cypher-machine.]
>
> The analyst has access to a captured table of keys to the cypher
> - but he doesn't know where the user started in his key table, so he tries
> starting positions one at a time, assuming consecutive keys were used
> for consecutive messages, as specified in the manual of a captured
> machine.
>
> Since the messages themselves are random, his only source of information
> is the padding used by the compressor. If he decyphers a large number of
> password files in a row, and they exhibit the same statistical anomalies
> that are introduced by the padding scheme of the compressor, he knows he
> has found the correct starting key.
>
> None of this would have bneen possible, were it not for a very few
> non-random bits information appended to the files.
>
> :> : In particular, periodicity will do perfectly well for my proposal.
> :> : Let's take the case where the plaintext (true one, or the wrong
> :> : one because of wrong decrypting key) is such that there need to
> :> : be 2 filling bits. Suppose the software is such that on the first
> :> : use it emits 00, the second time 01, the third time 10, the fourth time
> :> : 11, the fifth time 00, etc. Now suppose what the analysyt has after
> :> : decrpytion is a version with filling bits 00. He decompresses it
> :> : to the (presumed) plaintext and compresses that back again. There
> :> : are four different possibilties of the result. But in NO case can
> :> : he obtain any information, because he knows that any difference
> :> : is due to the 'ideosyncracies' of the compression software and
> :> : is not related at all to the 'proper' information in the file.
> :>
> :> That doesn't appear to be correct. Imagine the case where he has a
> :> complete known-plaintext attack on the cypher that recovers the key,
> :> and several consecutive known plaintexts. He can thus determine what
> :> padding bits have been used by the compressor. If he is intercepting
> :> all messages, he thus has information about what the padding bits are
> :> most likely to be on the next message, should that message require two
> :> padding bits. This is information he would not normally have, which may
> :> assist him with any attack.
> :>
> :> Of course, if he only has one message to work on, then - as you say -
> :> he's no better off.
>
> : In the example case mentioned above, all four filling bit patterns are
> : 'equally likely', there is no 'most likely' one. Could the analyst
> : still do something with his 'statistical data' of the filling bits?
>
> You said they were used in sequence. Consequently he knows that if the
> message has a two-bit padding - he knows which two bits will be used.
>
> Consequently some bits *are* more likely than other ones - despite each
> two-bit sequence being used with equal frequency.
>
> Can the attacker do anything with this? It's not very likely that he can
> do much with 1/4 of a bit. Analysts are clever folk, though. I wouldn't
> like to say it was always totally useless.
> --
> __________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> Mobius strippers never show you their back side.
I've been following this argument for a while now and find the whole
thing to be moot! The only time a generic Zipper becomes a problem is if
the encryption program that takes the zipped file and encrypts it
without changing the position of the BYTES. Take the following
example...
(read in 16k at a time...)
DIM MixBox(0 to 16383) as Integer
for x=0 to 16383
MixBox(x)=x
Next
k=Int(Rnd*1000) 'or something
for x=0 to 16383
k=(k+MixBox((x+13257))mod 16383 'or something like it
'now swap things around
c=MixBox(x)
MixBox(x)=MixBox(k)
MixBox(k)=c
Next
In the encryption routine you add...
cipher(x)=Plain(MixBox(x)) etc. etc
Now you have BYTE 15383 (or something) in peosition #1 of your
Ciphertext and BYTE 283 (o.s.) in position #2. After encryption I'd like
to see where the bad Zipper left its fingerprints so that a smart
attacker can use them to attack the file. Only a poor encryption algo
would leave the data where it found it. That is an invitation for a
plaintext (ziptext) attack!
Peter Rabbit
------------------------------
** 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
******************************
