finding key pairs with colliding fingerprints (Re: How thorough are the hash breaks, anyway?)
You would have to either: - search for candidate collisions amongst public keys you know the private key for (bit more expensive) - factorize the public key after you found a collision the 2nd one isn't as hard as it sounds because the public key would be essentially random and have non-negligible chance of finding trivial factors. (Not a secure backdoor, but still create a pretty good mess in DoS terms if such a key pair were published). The latter approach is what I used to create a sample dead-fingerprint attack on a PGP 2.x fingerprints. http://cypherpunks.venona.com/date/1997/06/msg00523.html (No need to find hash collision even tho' md5 because it has another bug: the serialization has multiple candidate inputs). So I just searched through the candidate inputs for one I can factor in a few minutes. Adam On Fri, Aug 27, 2004 at 12:22:26AM +0100, Ian Grigg wrote: Correct me if I'm wrong ... but once finding a hash collision on a public key, you'd also need to find a matching private key, right? If someone finds a collision for microsoft's windows update cert (or a number of other possibilities), and the fan is well and truly buried in it. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: How thorough are the hash breaks, anyway?
At 16:09 26/08/2004, Trei, Peter wrote: [snip] Looking over the recent work on hash collisions, one thing that struck me was that they all seem to be attacks on known plaintext - the 'plaintexts' which collided were very close to each other, varying in only a few bits. While any weakness is a concern, and I'm not going to use any of the compromised algorithms in new systems, this type of break seems to be of limited utility. It allows you (if you're fortunate) to modify a signed message and have the signature still check out. However, if you don't know the original plaintext it does not seem to allow you construct a second message with the same hash. [snip] From a lawyer's perspective, it seems worrying that a message into which the word not has been inserted might still have the same hash as the original (assuming the hash to be a component of an electronic signature) Regards Nicholas Bohm Salkyns, Great Canfield, Takeley, Bishops Stortford CM22 6SX, UK Phone 01279 871272(+44 1279 871272) Fax 020 7788 2198 (+44 20 7788 2198) Mobile 07715 419728(+44 7715 419728) PGP RSA 1024 bit public key ID: 0x08340015. Fingerprint: 9E 15 FB 2A 54 96 24 37 98 A2 E0 D1 34 13 48 07 PGP DSS/DH 1024/3072 public key ID: 0x899DD7FF. Fingerprint: 5248 1320 B42E 84FC 1E8B A9E6 0912 AE66 899D D7FF - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
| Bear writes:
| One interesting idea which I came up with and haven't seen a way
| past yet is to XOR each block with a value computed from its
| sequence number, then compute the hash function on the blocks in
| a nonsequential order based on the plaintext of the blocks
| in their new order.
|
| This is an interesting idea, but it does not fully prevent the Joux
| attack. This is seen most obviously in the two block case, where
| your method can at most increase the attacker's work by a factor of 2.
| Joux shows how to find a 4-collision using 2*2^(n/2) work, while it should
| take 2^(3n/4) work. In the case of a 160 bit hash this is the difference
| between 2^81 and 2^120. Doubling the work to find the 4-collision will
| not do much to address this discrepency.
|
| Even in the more general case, where Joux puts k blocks together to
| generate 2^k multicollisions, I can see a way to attack your method,
| with an increase in the work by only a factor of k^2
There's a more general problem with the algorithm: It isn't on-line. An
implementation requires either an unbounded internal state, or the ability to
re-read the input stream. The first is obviously impossible, the second a
problem for many common uses of hash functions (in communications, as opposed
to storage).
However ... *any* on-line algorithm falls to a Joux-style attack. An
algorithm with fixed internal memory that can only read its input linearly,
exactly once, can be modeled as an FSM. A Joux-style attack then is: Find
a pair of inputs M1 and M1' that, starting from the fixed initial state, both
leave the FSM in state S. Now find a pair of inputs M2 and M2' that, starting
from S, leave the FSM in state S'. Then for the cost of finding these two
collisions, we have *four* distinct collisions as before. More generally,
by just continuing from state S' to S'' and so on, for the cost of k
single collision searches, we get 2^k collisions.
The nominal security of the FSM is its number of states; for k large enough,
we certainly get too many collisions compared to a random function.
What this shows is that our vague notion that a hash function should behave
like a random function can't work. On-line-ness always kills that. (In
fact, even given the function random access to its input doesn't help: An FSM
can only specify a finite number of random places to look in the input.
If the FSM can only specify an absolute location, it can't work on arbitrarily
long inputs. If it can specify a location relative to the current position,
you can re-write the machine as a linear one that gets repeated copies of
blocks of a fixed size.)
This is really just the prefix property writ large. Define an on-line
function f:{0,1}*-{0,1}^k as one with the property that there exist
infinitely many pairs of strings Si, Si' with the property that, for any S in
{0,1}*, f(Si||S) = f(Si'||S). (In particular, this is true for S the empty
string, so f(Si) = f(Si').) Then the most we can expect of an (on-line)
hash function is that it act like a function picked at random from the set of
on-line functions. (This, of course, ignores all the other desireable
properties - we want to choose from a subset of the on-line functions.)
Getting a security parameter in there is a bit tricky. An obvious first cut
is to say an on-line function has minimum length n if the shortest Si has
length n.
Actual hash functions don't follow this model exactly. For example, MD5 needs
512+128+64 bits of internal storage* - the first for the input buffer, all of
whose bits are needed together, the second for the running hash state, the
third for the length. So there are 2^704 states in the MD5 FSM, but the
output only has 2^128 values - only 128 bits of the state number are used.
That in and of itself isn't an issue - it doesn't hurt, in this particular
analysis, to throw bits away in the *final* result. What does limit it is
that every 512 input bits, the FSM itself logically mods out 512 bits of the
state (the input buffer), and ends up in one of only 2^192 possible states
(and if we work with short strings, then only a small fraction of the 2^64
states of the length field are actually accessible). Because of this, MD5 can
at best have been chosen from on-line functions of minimum length 128, rather
than those of a minimal length up to 704. That's why keeping more internal
state *might* help - though you have to be careful, as we've seen, about how
you do it.
-- Jerry
* Actually, you need 3 more bits because the MD5 length is in octets, not
bits. This memory is hidden in any real implementation on byte-oriented
hardware.
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
Jerry Leichter writes: However ... *any* on-line algorithm falls to a Joux-style attack. An algorithm with fixed internal memory that can only read its input linearly, exactly once, can be modeled as an FSM. A Joux-style attack then is: Find a pair of inputs M1 and M1' that, starting from the fixed initial state, both leave the FSM in state S. Now find a pair of inputs M2 and M2' that, starting from S, leave the FSM in state S'. Then for the cost of finding these two collisions, we have *four* distinct collisions as before. More generally, by just continuing from state S' to S'' and so on, for the cost of k single collision searches, we get 2^k collisions. That's an interesting point. One counter example I can offer is my earlier suggestion to use a wide path internally between the stages. The analysis suggested that if the internal path was twice the width of the output of the hash, the Joux attack was avoided. Basically if the hash output width is n, and the internal width is 2n, then it will take 2^n to find an internal collision. And the overall hash strength is never more than 2^n against any attack, since you can exhaustively invert the function for that effort. So nothing based on internal collisions can weaken a hash built around this principle. It's not a particularly appealing design strategy due to its apparent inefficiency. But if you're right about the general vulnerability of hashes that support incremental hashing, as any useful hash surely must, then perhaps it is worth exploring. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Cryptography and the Open Source Security Debate
On Wed, Aug 25, 2004 at 03:17:15PM +0100, Ben Laurie wrote: lrk wrote: My examination of RSAREF and OpenSSL code was more toward understanding how they handled big numbers. It appears both generate prime numbers which are half the length of the required N and with both of the two most significant bits set to one. This means the ratio R=P/Q (P being the larger prime) is limited to 1R(4/3). The actual maximum R is less and can be determined by examining N. This doesn't sound right to me - OpenSSL, IIRC, sets the top and bottom bits to 1. Of course, all large primes have the bottom bit set to one. The source of OpenSSL I looked at was part of the FreeBSD distribution. int BN_rand(BIGNUM *rnd, int bits, int top, int bottom); BN_rand() generates a cryptographically strong pseudo-random number of bits bits in length and stores it in rnd. If top is -1, the most significant bit of the random number can be zero. If top is 0, it is set to 1, and if top is 1, the two most significant bits of the number will be set to 1, so that the product of two such random numbers will always have 2*bits length. If bottom is true, the number will be odd. It appears this is called with top=1 for RSA primes. OpenSSL may not use it that way. -- [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
| However ... *any* on-line algorithm falls to a Joux-style attack. An
| algorithm with fixed internal memory that can only read its input linearly,
| exactly once, can be modeled as an FSM. A Joux-style attack then is: Find
| a pair of inputs M1 and M1' that, starting from the fixed initial state, both
| leave the FSM in state S. Now find a pair of inputs M2 and M2' that, starting
| from S, leave the FSM in state S'. Then for the cost of finding these two
| collisions, we have *four* distinct collisions as before. More generally,
| by just continuing from state S' to S'' and so on, for the cost of k
| single collision searches, we get 2^k collisions.
|
| That's an interesting point. One counter example I can offer is my
| earlier suggestion to use a wide path internally between the stages.
| The analysis suggested that if the internal path was twice the width
| of the output of the hash, the Joux attack was avoided. Basically if
| the hash output width is n, and the internal width is 2n, then it will
| take 2^n to find an internal collision. And the overall hash strength
| is never more than 2^n against any attack, since you can exhaustively
| invert the function for that effort. So nothing based on internal
| collisions can weaken a hash built around this principle.
|
| It's not a particularly appealing design strategy due to its apparent
| inefficiency. But if you're right about the general vulnerability of
| hashes that support incremental hashing, as any useful hash surely must,
| then perhaps it is worth exploring.
It all depends on how you define an attack, and how you choose to define your
security. I explored the outer edge: Distinguishability from a random
function. For a random function from {0,1}*-{0,1}^k, we expect to have to do
2^k work (where the unit of work is an evaluation of the function) per
collision. The collisions are all independent - if you've found N, you have
... N. The next one you want still costs you 2^k work. However ... no on-
line function can actually be this hard, because a Joux-style attack lets you
combine collisions and find them with much less than the expected work.
Because a Joux-style attack works exponentially well, the cost for a very
large number of collisions is arbitrarily small. Note that this has nothing
to do with the number of internal states: One can distinguish random on-line
functions (in the sense I defined) from random functions (My criterion of
infinitely many extendible collision pairs may be too generous; you may need
some kind of minimum density of extendibile collision pairs.)
You can certainly de-rate such a function by discarding some of the bits
of the output and considering the range of the output to be {0,1}^l, l k.
But I don't see how that helps: In the limit, collisions become arbirarily
cheap, and making collisions easier can only decrease the cost of finding
them.
If the question is how close to the ultimate limit you can get a function
*constructed in a particular way*, then, yes, passing more internal state may
help. In fact, it's the only thing that can, if you want an on-line
algorithm - you have nothing else available to vary! A full analysis in this
direction, though, should have *two* security parameters: The current one,
the size of the output; and the amount of memory required. After all, MD5
(for example) is only defined on inputs of up to 2^64 bytes. If I allow 2^64
bytes of internal state, then the on-line qualifier becomes meaningless.
-- Jerry
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
Jerry Leichter writes:
It all depends on how you define an attack, and how you choose to define your
security. I explored the outer edge: Distinguishability from a random
function. For a random function from {0,1}*-{0,1}^k, we expect to have to do
2^k work (where the unit of work is an evaluation of the function) per
collision. The collisions are all independent - if you've found N, you have
... N. The next one you want still costs you 2^k work.
I don't believe this correct. Joux said that for a true random function,
finding a multicollision of degree j, i.e. j distinct values which hash
to the same thing, takes 2^((j-1)*k/j) for a k-bit hash. He mentioned
a Crypto paper by David Wagner from a few years ago which showed how
to do this. See http://www.cs.berkeley.edu/~daw/papers/genbday.html .
This means that the work for a (j+1)-collision is about 2^(k/j^2) times
harder than for a j-collision, not 2^k times harder.
Now, this is not done by first finding a j-collision and then looking
for a new value that matches; that would, as you say, take 2^k times
the work. Rather, one collects enough hashes and then matches them up
in an efficient way to find the (j+1)-collision.
The wide-internal-path proposal will therefore satisfy the constraints
about multicollisions. With a 2k bit wide internal path for a k bit hash,
it will take 2^k work to find an internal collision. With some multiple
of this, Joux's attack finds large multicollisions. But as the paper by
Wagner shows, you can find arbitrarily large multicollisions in a true
random k-bit function with less than 2^k work. Since Joux's attack
takes more than this, it does not distinguish this hash construction
from a random function.
Hal
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
