Subject: Re: New hash algorithms

From: "Bob Jueneman" <[email-masked]>
Date: Wed, 13 Sep 2000 08:37:54 -0600

>>> "Rob B Branch" <[email-masked]> 09/12/00 02:35PM >>>
>In reference to the below what does this new algorithm consist of?
Could you forward me the message that you ref. from Bill Burr?
Thanks in Advance...RobBranch

My apologies to the list.  I thought Bill had posted his comments to the
PKIX list -- actually, it took me a while to find it, as it was posted on a
list for the American Bar Association's Information Security committee. I
hope he won't mind me reposting it here.

His comment was made in the context of answering an attorney's question 
about the feasibility of breaking asymmetric keys vs. symmetric keys.

I believe that his intent was to strive towards a balanced approach to
cryptography, so that the strength of symmetric keys, asymmetric keys, and the 
message digest used within signature algorithms would all be approximately
equal.

Bob

Subject: Re: breaking PKI keys
From: Bill Burr <[email-masked]>
To: [email-masked]
Date: Wed, 30 Aug 2000 17:13:39 -0400

At 03:10 PM 8/30/00 -0400, Charles Merrill wrote:

>To analyze John Gregory's question, what does the cryptanalyst have to
>work with in order to derive the recipient's private decryption key from
>the corresponding public key, or the sender's private signing key from
>the corresponding public key?
>
>In the encryption case, the cryptanalyst has the symmetric ciphertext of
>the message, and the asymmetric ciphertext of the secret key.  If he can
>crack the asymmetric ciphertext to discover the plaintext of the secret
>key, then he can obtain the plaintext of that message. That will not
>reveal the asymmetric private key, but will provide both ciphertext and
>plaintext of one entire message for a known-plaintext attack.

Usually the analyst is going to attack the weak link.  If the symmetric key
algorithm is 3DES, with a 112-bit key, and the asymmetric key algorithm is
1024-bit RSA, every indication is that it's easier to factor a 1024-bit
number than crack a 112-bit 3DES key.  Moreover cracking the 112-bit 3DES
key gives you one message, while the RSA key gives you lots of message.  Of
course, as far as is publicly known, neither 1024-bit RSA nor 112-bit 3DES
has ever been successfully attacked, to date.

If the symmetric key algorithm were 56-bit DES, or old 40-bit "exportable"
symmetric key encryption, then the symmetric key encryption would probably
be the weak link.

There are chosen plaintext attacks against DES with nominal workfactors
less than key exhaustion, but, as a practical matter it's probably easier
in almost every case to attack DES by key exhaustion.

>
>In the signature case, the cryptanalysis has: the plaintext of the
>message, the plaintext of its hash result (by himself running the
>plaintext of the message through the publicly-known hash algorithm), and
>the asymmetric ciphertext of the hash result of the message.  The hash
>result is typically the (almost unique) representation of a much longer
>message.  He will have both plaintext and ciphertext of the hash result
>without difficulty, but no asymmetric ciphertext of the longer message.

Factoring attacks on RSA public keys are basically the same whether they
are encryption keys or signature keys.

There is another attack on a signature, by finding two message texts that
hash to the same value.  It's not necessarily easy to figure out how to
conduct such an attack in a practical way, but the average workfactor to
find two messages with the same 128-bit MD5 hash, is only 2^63, which is
verging on a practical thing now, and for a 160-bit SHA-1 hash it's 2^79,
which is considerably harder.  Still, if we're talking about using 112-bit
3DES and 128, 192 and 256-bit AES encryption, the 160-bit hash now becomes
something of a weak point.  If we're encrypting a 160-bit hash in a with
2048 bit RSA for a signature, it's probably not very much stronger than
that same 160-bit hash encrypted with a 1024 bit RSA key.

At NIST we're planning to propose new, stronger hashes of 256, 384 and 512
bits (to be called SHA-256, SHA-384 and SHA-512) that will be roughly as
strong as 128, 192 and 256 bit AES respectively.  These would be used with
RSA key sizes of 2048 bits or more to make stronger signatures.

>On balance, a known-plaintext attack to discover an asymmetric private
>key used EITHER for signing or for decryption strikes me as not as
>fruitful than working with the public key alone.  That leaves brute
>force factoring of the product of two huge prime numbers (possibly
>through vastly faster computation methods many years in the future),
>possible mathematic shortcuts still to be discovered, chip anomalies or
>chip peeling, exploitation of known or guessed mathematical bias or
>other defects in the key generation process, and the like.
>
>Chas (a determined studier of Schneier's "Applied Cryptogrpher", but
>otherwise far beyond my depth)
>Attachment Converted: "c:\eudora\attach\cmerrill1.vcf"
>
Regards,

Bill Burr

To unsubscribe send the following in the body of a message to
[email-masked]  - unsubscribe st-isc

---

From: "Bob Jueneman" <[email-masked]>
Date: Wed, 13 Sep 2000 09:40:41 -0600

"Jeff Davis" <[email-masked]> 09/13/00 05:06AM >>>
>Bob,

>I am new to this but my understanding of Hash values were that they
would be dramatically different if a single bit was to change inside the
data that was being hashed.  Therefore, finding a duplicate hash value
would not be of any use as the data that produced it would be
significantly different in content and context to the original.  Thus,
if an attacker wanted to change a little data within a very sensitive
"transaction" then to create a hash value of that changed data, it would
be impossible to come up with the same hash value as the original.  The
digital signature would then expose the change.

>Can you explain to me, in brief if possible, what an attacker would gain
from finding a duplicate hash inside 2^64 or 80?.  Help understanding
this would be appreciated as I feel I am missing something.

>Cheers

>Jeff Davis

Hi, Jeff,

You are correct -- any decent secure hash function or message 
digest will have the property that if so much as a single bit changes, 
moves, or is added or deleted to the original message, the entire hash 
result changes, so that the probability of any particular bit of the result
is the same is 50%.  Moreover, it is computationally infeasible to 
_derive_ (from the hash value), either the original 
message, or another message that would be different from the 
original but would have the same hash value.

And of course, if you are trying to find or create a new message which
produces the same hash result as a given (fixed) message, you are
going to have to do an exhaustive search over the entire message 
space. With a 160-bit hash such as SHA-1, you would be facing 
a 2^159 exhaustive search -- certainly infeasible.

However, there is another attack that is subtle but dangerous,
and newcomers to the field may not have encountered it.

Early on in the development of public key technology, Rabin 
suggested the use of a message digest or hash function 
to simplify the calculation of a digital signature.

But in a famous article entitled "How to Swindle Rabin,"
which appeared in Cryptologia (v.3, n.3, Jul 1979, p 187-190),
Gideon Yuval proposed the following attack:

1.  Alice prepares two versions of a contract: one is favorable to 
Bob, and the other to Alice.

2.  Alice makes a series of subtle changes to both documents --
changes that would not be noticeable by Bob. For example, 
one or more spaces might be inserted at the end of a line, or 
in some systems a space-backspace-space sequence might be 
inserted. (Word processing documents with proportional spacing 
introduce all sorts of opportunities to diddle the spacing between 
characters or words, change font size slightly, etc.) By doing making
these indiscernible modifications on only 64 lines, 2^64 different 
versions of each document can be created, and the hash calculated.

3.  After producing all of the variations of both documents, Alice
sorts or otherwise compares the message number and the hash value, 
looking for two message variants that hash to the same value.
According to the Birthday Problem in statistics, Alice has 
approximately a 50% chance of finding at least one duplicate 
after sqrt(N)/2 tries, where N is the number of possibilities.
For a 128-bit hash value, therefore, the 50% probability point is 
approximately 2^63 samples, and the chance of success rises 
very sharply after that point.

4.  Having found two matching hash values, she sends the 
corresponding variant of the document that is favorable to Bob 
off to him to be signed, which he does to indicate his consent.

5.  At some time in the future, Alice produces the version of the 
document that is favorable to her, along with Bob's digital signature
containing an identical hash, and somehow convinces the judge 
that her version is the legitimate one.  

(A moral to this story is that Bob should make some kind of a 
cosmetic change to any document he signs, and he should always 
keep a copy of that document.)

This same attack would conceivable apply to ANY kind of a digital 
signature which is computed over a message digest or hash, including
of course X.509 certificates.

At present, it appears that a 1024-bit RSA signature would be about 
as hard to factor as an 80-bit symmetric key would be to break via a 
exhaustive search attack.  

Therefore, neglecting the cost and difficulty of storing and searching
the required amount of data, this suggests that a hash algorithm that is 
used in combination with a 1024-bit RSA key (or other algorithm of 
equivalent strength) should be DOUBLE the size of the equivalent
symmetric key strength, or about 160 bits.

This suggests that SHA-1 is about right for a 1024-bit RSA signature,
but would be too short for a 2048 bit key, much less anything longer.
it also suggests that a 128-bit MD5 hash is already too short for safety.

So it is probably time to start thinking about longer hashes, just as it it time
to start thinking about longer than 1024-bit signatures.

Bob

---

From: "Jeff Davis" <[email-masked]>
Date: Wed, 13 Sep 2000 21:25:52 +0100

Bob/Byron

Many thanks for your explanations, I now understand much better.

Jeff

<Original messages cut>