Re: Please explain in simple terms -- key collision attack

As I wrote in my original posting, I didn't find a free copy of the
Biham paper in question.

I believe the relavant paper is titled, "How to Decrypt or Even
Substitute DES-Encrypted Messages in 2^28 Steps" in Information
Proccessing Letters 84, (2002) 117-124.

According to this paper

http://eprint.iacr.org/2002/159.pdf

by Loughran and Dowling, what the Biham paper proposes is exactly what
you wrote.

"Applying this to our attack, n=2^56 and it is only necessary to have
two collections of 2^28 ciphertexts to have a high probability of
finding a matching pair of ciphertexts."

If loughran and Dowling correctly understood Biham, then your objection
should be taken up with Biham.

The gentleman asked what the attack was, and I did my best to answer
his question correctly.

David Sexton

Unruh wrote:
"da5id65536@xxxxxxxxx" <da5id65536@xxxxxxxxx> writes:

It's really a kind of known-plaintext attack. Many types of files
always begin with some kind of header. Encrypt the header with many
keys (enough for the Birthday Paradox to be significant). Then wait
for one of the keys to be used. Apparently, in the 2002 paper I assume
you refer to (I didn't find a free copy of it, but did find references
to it), Biham proposes storing a header encrypted with 2 to the 28th
different keys in order to attack plain DES with 56 bit keys.

This makes little sense unless there really are a huge number of different
keys out there.

The probability of hitting one of those keys for each external key is
2^{-28}. Since one has no guarentee that the external keys are all
different, the probability of hitting it once in n tries is
1-(1-2^{-28})^n = 1-exp(2^{-28}n). Thus n has to be at least 2^28 for this
to have any probability of success.
Ie, one would need 2^28~10^9 messages of the same header encrypted with
different keys for this to pay off once.


David Sexton

AM wrote:
Hi all:

Would somebody take time to explain in simple terms what a "key
collision attack" mean? And, the summary of Biham key collision attack?

Thanks!
AM

.

Relevant Pages

  • Re: SHA1 broken
    ... >> probability of occuring above a given threshold. ... When the diff occurs only a limited subset of keys are possible. ... for all p then the attack can't work. ...
    (sci.crypt)
  • Re: A basic cryptanalysis question
    ... >> appear out of his attack, he assumes he's recovered the plaintext. ... >include the keys in your construction. ... such a function look at my second order bijective compression of english ...
    (sci.crypt)
  • Re: how secure is SSL?
    ... Most SSL protocols in practice are using 1024-bit RSA keys. ... Untrusted code is another, extra huge problem. ... the number of linearly independent equations. ... Well, if this particular attack is flawed, I don't know. ...
    (sci.crypt)
  • Re: Sort benchmark and a classic paper by Gray
    ... Statistical complexity theory predates computer science, ... of the keys not being too evil, ... This is of course a hash table, with the additional benefit of knowing ... provably Owith probability one in the number of operations. ...
    (comp.arch)
  • Re: [Full-disclosure] Firewire Attack on Windows Vista
    ... shorten the window of attack for a specific type of user but it's mostly ... Microsoft claims that hibernate mode clears the cryptographic keys from ... my point was _not_ that in a very specific configuration you're ...
    (Bugtraq)