Cryptography-Digest Digest #827, Volume #10 Sun, 2 Jan 00 21:13:01 EST
Contents:
Re: meet-in-the-middle attack for triple DES (Mok-Kong Shen)
Re: cracking Triple DES (David Wagner)
Re: RFC1750: Randomness Recommendations for Security (1 of 2) (Mok-Kong Shen)
Re: meet-in-the-middle attack for triple DES (Bill Unruh)
Re: cracking Triple DES (Mok-Kong Shen)
Re: meet-in-the-middle attack for triple DES (Bill Unruh)
Re: vigenere decrypt routine - help needed (Bill Unruh)
Re: stupid question (Guy Macon)
Re: Wagner et Al. (Guy Macon)
test ("Jester")
Re: meet-in-the-middle attack for triple DES (Scott Fluhrer)
Re: Wagner et Al. ("Daniel Roethlisberger")
Re: encryption algorithm with 21-character results? (David Hopwood)
Re: RFC1750: Randomness Recommendations for Security (1 of 2) (Michael Sierchio)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: meet-in-the-middle attack for triple DES
Date: Sun, 02 Jan 2000 22:17:58 +0100
P. Daniel Suberviola, II wrote:
>
> This is wonderful, but how would it help in the real world? It seems to me
> like circular logic; if you already know the plaintext and ciphertext, what
> good is it to know the keys? Further, how would this help you in real life
> over a brute-force attack, since when you really need to break something you
> will know absolutely nothing except for the ciphertext and the keys are sure
> to be different?
If one could manage to have each block encrypted by a different key,
then such attacks would in my humble opinion be pointless for any
common block encryption algorithm that offers sufficient difficulty
to determine the key from only one single pair of corresponding plain
and cipher texts. On the the further assumption that the key stream
is not (or barely) subjected to inference, this would seem to leave
the adversary no other means in practice but to brute force the
'key' that generates the said key stream. (Note that the key stream
is used 'indirectly' here, in distinction to its usage in common
stream encipherments.) Other techniques like the differential analysis
would be useless for the same reason, as I argued previously. I
should very much appreciate comments, if there are flaws in the
above line of humble thoughts of mine.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: cracking Triple DES
Date: 2 Jan 2000 14:14:18 -0800
In article <[EMAIL PROTECTED]>,
John E. Gwyn <[EMAIL PROTECTED]> wrote:
> DJohn37050 wrote:
> > Attack in the middle. Attack one pair of keys with 2**112 and the
> > other with 2**56 and look for matches.
>
> Easier said than done. How are you going to implement "look for
> matches"? Store 2^56 blocks of on the order of 64 bits each, or
> set up a hash table that big?
van Oorschot & Wiener's `parallel collision search' is useful here.
See their paper on speeding up meet-in-the-middle attacks by orders
of magnitude; I think it was in a recent CRYPTO proceedings.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: RFC1750: Randomness Recommendations for Security (1 of 2)
Date: Sun, 02 Jan 2000 23:44:56 +0100
Tiny remarks:
1. If I don't err, lossless compression on sufficiently 'random'
sequences might even result in expansion instead of compression with
some compression schemes.
2. BBS probably might not be so good as its fame in the literature
suggests. See Terry Ritter's web page.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: meet-in-the-middle attack for triple DES
Date: 2 Jan 2000 22:54:13 GMT
In <386d279e$0$[EMAIL PROTECTED]> "P. Daniel Suberviola, II" <[EMAIL PROTECTED]>
writes:
>According to Schneier,
>C = EK3(DK2(EK1(P))) and P = DK1(EK2(DK3(C))).
>That part makes sense. However, he claims that there is a
meet-in-the-middle
>attack to break this. Could someone please briefly explain to me how
this
>would be done?
Known plaintext. For all keys 1 2 3, evaluate and store
Y(k1,k2)= Dk2(Ek1(P))
Z(k3)=Dk3(C)
Search through list to Find k1,k2 and k3 such that Z(k3)=Y(k1,k2)
Requires just 2^( L(k1)L(k2)+L(k3)) instead of 2^(L(k1)L(k2)L(k3))
encryptions. But requires huge storage space.(2^(L(k1)L(k2))). ( L(k1)=
length o
f key 1 )
>This is wonderful, but how would it help in the real world? It seems to
me
>like circular logic; if you already know the plaintext and ciphertext,
what
>good is it to know the keys? Further, how would this help you in real
life
>over a brute-force attack, since when you really need to break
something you
>will know absolutely nothing except for the ciphertext and the keys are
sure
>to be different? I'd appreciate it very much if someone could clear all
of
>this up for me.
No you often do know a bit of the plain text ( a crib), and you want to
know it all. For example each message could start with a salutation
say "Heil Hitler" which you know for some other reason. Then you use
that little bit of knowledge to figure out the key and thus read
everything.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: cracking Triple DES
Date: Sun, 02 Jan 2000 23:59:53 +0100
David Wagner wrote:
>
> John E. Gwyn <[EMAIL PROTECTED]> wrote:
> > DJohn37050 wrote:
> > > Attack in the middle. Attack one pair of keys with 2**112 and the
> > > other with 2**56 and look for matches.
> >
> > Easier said than done. How are you going to implement "look for
> > matches"? Store 2^56 blocks of on the order of 64 bits each, or
> > set up a hash table that big?
>
> van Oorschot & Wiener's `parallel collision search' is useful here.
> See their paper on speeding up meet-in-the-middle attacks by orders
> of magnitude; I think it was in a recent CRYPTO proceedings.
In my humble opinion one simple and direct means of counteracting
such attacks is to use variable keys, i.e. employing different keys
for different blocks. This in effect would 'define away' the
possibility of such attacks in the first place.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: meet-in-the-middle attack for triple DES
Date: 2 Jan 2000 22:59:22 GMT
In <[EMAIL PROTECTED]> Mok-Kong Shen <[EMAIL PROTECTED]> writes:
]If one could manage to have each block encrypted by a different key,
]then such attacks would in my humble opinion be pointless for any
]common block encryption algorithm that offers sufficient difficulty
]to determine the key from only one single pair of corresponding plain
]and cipher texts. On the the further assumption that the key stream
]is not (or barely) subjected to inference, this would seem to leave
]the adversary no other means in practice but to brute force the
]'key' that generates the said key stream. (Note that the key stream
Sure, but it will be slow. If your key stream is sufficintly strong,
then just xor will probably be fine. many block encryptions take a long
time to set up the key schedule, and you have to go through this for
each and every block.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: vigenere decrypt routine - help needed
Date: 2 Jan 2000 23:10:09 GMT
In <[EMAIL PROTECTED]> Mike Todd <[EMAIL PROTECTED]> writes:
> I`m trying to write a vigenere-polyalphabetic decrypt routine in Java,
>but I`m having bother getting the probable length of the key. If anyone
>knows/has a routine to decrypt the vigenere that I could refer to I`d be
>grateful.
As described in Singh's book The Code Book, you break it by looking for
repetition frequencies for long letter string (ie at least 3 or 4
letters as it is unlikely that you would get a repetition of a "random
stream" by chance with that may letters.) Since there are probably a few
such repetitions, you can work out the minimum period and thus find the
length of the code word. Then each subsection is just a ceasar cipher,
which can be solved by frequency analysis. On the other hand, there are
not that many three or four letter combinations which you would expect
to repeat so many times in the text. (eg for a 6 letter code word if you
find two repetitions in the text the probablility is that that string of
letters actually repeats 12 times in the actuall text -- only two
actually line up.)
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: stupid question
Date: 02 Jan 2000 18:36:09 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (John E. Gwyn)
wrote:
>
>Buchinger Reinhold wrote:
>> I have a stupid question. But what is the difference between a key
>> of a stream cipher and a key of an one-time-pad ???
>
>It's not such a stupid question; people have confused the issue
>by misapplying the terms..
>
>A stream cipher produces an output symbol for each input symbol,
>without having to buffer up input symbols into a block before
>encrypting them. (The other design is called, appropriately, a
>"block cipher".)
I am not sure how to interpet "symbol". If I take a plaintext
and an equally sized randomtext (if such exists) and exlusive
or them to create my ciphertext, I can treat the two input streams
as a series of bits. If I replace the XOR with various other
combining methods, I need to treat the two input streams as a series
of bytes. If I use Unicode. bytes are too small. I can imagine
working on a series of 1K graphics files that each display a single
letter. Would a "block" cipher with 1K blocks become a stream cipher
in the case of the graphics files? This is a silly example, but my
question is real - I don't think that I can define the difference
between a stream and block cipher with rigor.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Wagner et Al.
Date: 02 Jan 2000 19:11:23 EST
In article <84nicv$l70$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tom St Denis) wrote:
>Now let me ask you, how would you intercept a windows message? Via a
>trojan? Probably. What if I told you I could write a trojan to take
>snapshots every 5 seconds and send it to me. Basically you can't
>protect against trojans, so I didn't really try to. I think that line
>of attack is moot since well most people are smartenough to avoid
>programs that may have trojans [such as email greating cards]
As with most security issues, this depends on what kind of
attacker you are trying to stop. In some cases, You might
have someone willing to break in and put something on your
computer, make a fake driver update and send it as a legit
looking floppy, etc. In addition, holes keep showing up in
Microsoft applications that could allow an attacker to plant
a trojan without you ever knowingly running an executable.
It is possible to have better security than your system
provides. I have a 486 PC with DOS, my encryption
program, and the best info wiping program that I know of
on it. My plaintext is created and encrypted on this box,
and the plaintext is only stored on a floppy in my A: drive
that gets a multipass secure wipe and several formats after
the encryption. I transfer my ciphertext on another floppy
in drive B:. I can also throw the wiped A: floppy in my
fireplace if I want to be really sure. My encryption batch
files also check for changes in the amount of free memory
or free hard disk space, and "one of these days" I am going
to expand this to doing a checksum of some sort. None of
this protects me against a dedicated attacker, and it is
overkill against my probable opponent (I really don't have
one - I just do this sort of thing as a hobby), but if I
added physical security, I would be in fairly good shape.
------------------------------
From: "Jester" <[EMAIL PROTECTED]>
Subject: test
Date: Sun, 2 Jan 2000 17:14:56 -0700
test
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: meet-in-the-middle attack for triple DES
Date: Mon, 03 Jan 2000 00:23:23 GMT
In article <84okul$ka9$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bill Unruh) wrote:
>In <386d279e$0$[EMAIL PROTECTED]> "P. Daniel Suberviola, II" <[EMAIL PROTECTED]>
>writes:
>>According to Schneier,
>
>>C = EK3(DK2(EK1(P))) and P = DK1(EK2(DK3(C))).
>
>>That part makes sense. However, he claims that there is a
>meet-in-the-middle
>>attack to break this. Could someone please briefly explain to me how
>this
>>would be done?
>
>Known plaintext. For all keys 1 2 3, evaluate and store
>Y(k1,k2)= Dk2(Ek1(P))
Actually, there's no need to store the Y(k1,k2) values, you can search
for them in the Z(k3) list as you generate them.
>Z(k3)=Dk3(C)
>Search through list to Find k1,k2 and k3 such that Z(k3)=Y(k1,k2)
>Requires just 2^( L(k1)L(k2)+L(k3)) instead of 2^(L(k1)L(k2)L(k3))
>encryptions. But requires huge storage space.(2^(L(k1)L(k2))).
No, 2^L(k3) storage.
In general, a meet-in-the-middle attack on a system C = EKB(EKA(P))
takes O(2^max(L(KA),L(KB))) time and O(2^min(L(KA),L(KB)))) space.
For 3DES, you take:
EKA(P) = DK2(EK1(P))
EKB(P) = EK3(P)
--
poncho
------------------------------
From: "Daniel Roethlisberger" <[EMAIL PROTECTED]>
Subject: Re: Wagner et Al.
Date: Mon, 3 Jan 2000 01:52:14 +0100
>Now let me ask you, how would you intercept a windows message?
>Via a trojan? Probably. What if I told you I could write a trojan to
>take snapshots every 5 seconds and send it to me. Basically you
>can't protect against trojans, so I didn't really try to. I think that
>line of attack is moot since well most people are smartenough to
>avoid programs that may have trojans [such as email greating
>cards]
I don't think that's the point, whether users will be smart enough. You
always have to expect the worst anyway. You'd be surprised how stupid the
general user is. If you got no trojans running on your system, then that's
fine. But you cannot expect everyone else hasn't.
Decent encryption software cares for its sensitive data. It locks memory in
which it allocates memory for keys and such, so it doesn't get paged on hard
disk. It wipes memory after usage. It also tries not to send it through
windows mechanisms like the windows messages.
Of course you can say: I only care about the externals, the encrypted files,
disks or communication. The user has to keep his own computer secure. But
what if the user isn't the only person working on a given computer? What if
the laptop gets stolen? What if the user lets his computer unattended in
office for a couple of hours? Anyone could install whatever he/she wanted on
it.
I think it crucual to make an encryption software as hard to attack as
possible. What use is decent cryptography if the rest of the software is
easily attacked? The implementation of the ciphers can be as secure as they
want, if someone can easily get to the keys, the security is lost. That's
like encrypting the hard disk using a very strong cipher and storing the key
in plaintext someplace where everyone can get to it...
Giving up on trojans is not the right way. There *are* ways to defend
against trojans. One thing is to make every software as secure as possible.
Of course MS has made a bad example at windows security, but you can still
make your own software secure. Another is to follow safe computing
practices. Many users don't even run an AV scanner on their systems, not to
think of firewalls and the like.
/Dan
------------------------------
Date: Mon, 03 Jan 2000 00:17:22 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: encryption algorithm with 21-character results?
=====BEGIN PGP SIGNED MESSAGE=====
Can Leonard wrote:
>
> I dont know if i formulated the subject line that well, but here's the
> basic outline:
>
> I'm working on a unix version of the online chat program "Yahoo
> Messenger", and I have code that worked for an older protocol version,
> but need to figure out the new protocol (no documentation) before I can
> actually write the "pretty" stuff..
>
> The authentication mechanism _used_ to be that the client connected to
> an HTTP server, got a cookie,, and then sent a subset of that cookie to
> the actual chat server as its authentication string... The new protocol
> seems to ignore the cookies and instead sends an "encrypted(?)" string
> such that:
>
> - for two different users with the same password, the string sent is the
> same;
> - there seems to be a fixed "header" of sorts that is shared across all
> encrypted passwords (but I havent tested that many of them to know if
> that really holds).
> - the fixed string appears to be: $1$_2S43d5f$
> - In addition, the encrypted password seems to be comprised of
> upper/lower case characters + digits + '.' + (perhaps other stuff that I
> didnt come across)
+ '/', I think.
> - the portion following the header has a fixed length of 21 characters,
> followed by a terminating "/\001" (that is, '/' followed by '\001')
I recognise this format; excluding the final \001, it's the MD5 variant
of BSD crypt(3). See
http://www.openbsd.org/cgi-bin/man.cgi?
query=crypt&sektion=3&apropos=0&manpath=OpenBSD+Current
They're using it in about the weakest possible way, though - the salt
should be different for each user.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOG/qdjkCAxeYt5gVAQHkvAf+M+JBKaAq9SLqf2YlB0ceFlo7Ex8l9A0Y
u2kDmXV6PR6EYebq2/M5xbJAvJeM0C4sFZJL5QIVGOxefPiJZq6FitiKyKTIiH4U
CObAF7rdlIdZ/918J0O5ebWLSg3Mzh6NNbz7r4fqQgxt0Y4BHlI7d0cre/pcFnL0
BkV2NJedK/sOUU/TbgOxsjwqNlaA01W8NCVcf20ztHPKBbiRecLyjHjgVPm+UtpF
HwUlDHcqYamktVRLPEf9W6e4LajNkNZrlBtR+izoWGBI6p4PfRzMkRJnbqO3+PXb
CRS22eSMJXyxmdQ18W/FEsMw5Nfy4RCQTNPdBfQNyQPIz90NoZYV+g==
=VndL
=====END PGP SIGNATURE=====
------------------------------
From: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: RFC1750: Randomness Recommendations for Security (1 of 2)
Date: Sun, 02 Jan 2000 17:36:24 -0800
Mok-Kong Shen wrote:
> 2. BBS probably might not be so good as its fame in the literature
> suggests. See Terry Ritter's web page.
Right - direct links to Terry's articles on BBS here:
http://www.io.com/~ritter/NEWS2/TESTSBBS.HTM#BB&S
http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect4.4
There are numerous problems with BBS - the selection of the primes,
for example, is *not* simply a matter of choosing two primes that are
equivalent to 3 mod 4. Read Terry's comments. To satisfy the conditions
for the quadratic residue generator that is guaranteed to have long
cycles, you need to select 2 special primes of the form
P = 2*P1 + 1, P1 = 2*P2 + 1 & Q = 2*Q1 + 1, Q1 = 2*Q2 + 1
where P, P1, P2, Q, Q1, Q2 are prime, and only one of P1, Q1 has 2
as a quadratic residue.
Once you've selected such primes, the problem of seeding the
generator is immense. You can't select a random value -- it might
be on a short cycle.
--
QUI ME AMET, CANEM MEUM ETIAM AMET
------------------------------
** 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
******************************
