. 1
( 19 .)



>>

Previous Page Home Next Page




On Recent Results for MD2, MD4 and MD5 ........... 1
1. Introduction 2. Hash Function Properties ....................... 1
3. Hash Function Structure ................................................ 2
4. The Status of MD2 ......................................................... 3
5. The Status of MD4 ......................................................... 3
6. The Status of MD5 ......................................................... 3
7. Some Alternative Hash Functions .................................. 4
8. Summary and Conclusions ............................................ 5
References ......................................................................... 6
Proper Initialization for the BSAFE Random Number ...... 7
Abstract .............................................................................. 7
Timing Attacks on Cryptosystems .................................... 9
Summary ............................................................................ 9
Impact on RSA Data Security Products ............................. 9
Countermeasures .............................................................. 10
Asymmetric Encryption: Evolution and Enhancements .. 11
PayWord and MicroMint ..................................................... 17
The HMAC Construction .................................................... 21
RSA for Paranoids ............................................................... 26
Conventional RSA .............................................................. 26
About RSA laboratories ..................................................... 27
Unbalanced RSA ............................................................... 28
Other optimizations ............................................................ 28
Collisions in MD4 ............................................................... 29
How Alf did it ...................................................................... 30
More Developments with Keyed Hash Functions .............. 31
A linear Protocol Failure for RSA ....................................... 31
The Secure Use of RSA ....................................................... 32
The RSA Cryptosystem ..................................................... 32
Aims of the Attacker ........................................................... 32
Recovering the Private Key ............................................... 33
Wiener•s Attack .......................................................................... 34
Using Probabilistic Primes .......................................................... 34
Decrypting Messages ........................................................ 34
Small Messages ......................................................................... 34
Chosen Ciphertext Attacks ......................................................... 34
Previous Page Home Next Page



Low Exponent Attacks ................................................................ 35
Forging Signatures ............................................................. 35
RSA Block Formats ............................................................ 36
Conclusions ....................................................................... 37
References ......................................................................... 37
PKCS #l Block Formats ..................................................... 37
F R E Q U E N T L Y A S K E D Q U E S T I O N S .......... 39
How Do Digital Time-StampsSuppolt Digital Signatures? .......... 39
References ................................................................................. 40
The 1996 RSA Data Security ..................................................... 41
Elliptic Curve Cryptosystems ............................................. 42
Alfred Menezes .................................................................. 42
Discrete-log cryptosystems ................................................ 42
Editors Note ...................................................................... 43
Subscription Information ............................................................. 43
Elliptic Curve Cryptosystems ............................................. 44
Why consider other groups? ...................................................... 44
Elliptic curves ............................................................................. 44
References ................................................................................. 45
STANDARDS UPDATE ..................................................... 45
Elliptic Curves in Draft IEEE Standard ....................................... 45
S/MIME Standardized ................................................................ 45
The Future of Integer Factorization .................................... 46
AndxewM.Odlyzko ...................................................................... 46
Introduction ................................................................................. 46
Factorization records and historical estimates ....................... 46
Projections of computing power available in the future ......... 46
Algorithmic improvements ..................................................... 48
Factorization using current algorithms ................................... 48
Acknowledgements ................................................................ 49
References ............................................................................ 49
Conclusions ........................................................................... 49
Appendices ............................................................................ 50
Appendk A: Historical estimates of the difficulty of factoring ............ 50
Appendix C: Gomputing power of historical factorizations ............... 51
Appendix E: Moores Iaw ............................................................... 51
Appendix D: Current computing power ............................................ 51
Appedix F: Number of computers ..................................................... 51
Appendix H: Comparison of running times of algorithms ................. 52
Appendhix G:Running time of algorithms ......................................... 52
AppedixJ: Attacks on DES ............................................................... 53
On the Security of the RC5 Encryption Algorithm .................. 54
References ....................................................................................... 55
ALG0RITHM SUPDATE ........................................................ 55
MD5 Performance for IP Security Questioned ................................. 55
Previous Page Home Next Page



Further Comments on Keyed MD5................................................... 56
A N N 0 U N C E M E N T S .................................................. 57
RSA Laboratories Technical Reports ............................................... 57
The 1996 RSA Data Security Conference 1996 17-19 .................. 57

The Impending Demise of RSA? ........................................ 58
GilksBrassard ..................................................................... 58
Welcome to CryptoBytes .................................................. 59
Subscription Information ............................................................. 59
The Impending Demise of RSA? ....................................... 60
Message Authentication with MD5 ..................................... 62
Recommendations ............................................................. 63
Starting over ....................................................................... 65
References ......................................................................... 65
The RC5 Encryption Algorithm* ......................................... 66
Ronald L Rivest .......................................................................... 66
Introduction ................................................................................. 66
Overview of the Algorithm .......................................................... 66
Encryption and Decryption ......................................................... 66
Key Expansion 3 ........................................................................ 67
Speed ......................................................................................... 67
Security ...................................................................................... 67
References ................................................................................. 68
N E W SA N D I N F 0 R M A T I 0 N ................................. 68
X9Fl Considers Triple-DES Standard ......................................... 68
RSA Laboratories Publishes PKCS #l 1 ..................................... 68
A N N 0 U N C E M E N T S ............................................... 69
1995 RSA Laboratories Seminar Series .................................... 69
RSA Laboratories Technical Reports ......................................... 69

Suggestions for Random Number Generation in ..... 70
Introduction ........................................................................ 70
Random vs. Pseudo-Random Numbers ............................ 70
The Seed ........................................................................... 71
Example ............................................................................. 72
Further Reading ................................................................. 73
Conclusion ......................................................................... 73
Page 1
Previous Page Home Next Page
NUMBER 4 -NOVEMBER 12, 1996
I




News and advice from RSA Laboratories




On Recent Results for MD2, MD4 and MD5
this note is intended to summarize these results and
M.J.B. Robshaw
their impact. First however we will consider the
RSA Laboratories
properties of hash functions. An important issue, that
we will repeatedly stress, is that not all applications
Abstract. Recent cryptanalytic results on the properties of three
of a hash function rely for their security on the same
popular hash functions have raised questions about their secu-
property. Consequently, identifying which property
rity. This note surnmari˜es these results, gives our assessment of
of a hash function is appealed to within an imple-
their implications and offers our recommendations for product
mentation is very important and sometimes leads to
planners and developers who may be using these algorithms.
surprising results.
1. Introduction
2. Hash Function Properties
A hash function (or more accurately a cryptographic
hash function or message-digest algorithm) operates on Hash functions are designed with a variety of prop-
an input string of arbitrary length and generates an erties in mind and three are commonly singled out
output string of fixed length. This output is common- in the literature [18].
ly called a hush value or a message digest. While much
of the motivation for the design of a hash function First, given the hash value output by some hash func-
comes from its usefulness in optimizing the process tion, it should be infeasible to find an input or
of digitally signing some document, hash functions weimage that will produce the given output. A slight
can be used for a wide range of purposes. variation on this gives a second condition which is
that even when given an input and output pair for
MD2 [13], MD4 [20] and MD5 1211 are hash func- some hash function, it should remain infeasible to
tions that were developed by Ron Rivest at MIT for find a second distinct preimage that would generate
RSA Data Security. A description of these hash func- the same output. This is commonly referred to as
tions can be found in RSA Laboratories Technical finding a second preimage and a hash function for
Report TR-101 [22]. The widespread popularity of which it is difficult to find either a preimage or a
the MD family of hash functions is a testament to second preimage is sometimes called a one-way hash
their innovative and successful design. Indeed MD4 function [ 181.
in particular has been used as the basis for the design
of many other hash functions (including MD5, A third condition that is sometimes required is that
SHA-1, RIPEMD) and MD5 is one of the most it be infeasible to find two inputs to the hash func-
widely used hash functions in the world today. tion that will produce the same output. This is com-
monly referred to as finding a collision for the hash
Over the years, various results in the cryptanalysis of function. Since there are an arbitrary number of
MD2, MD4 and MD5 have become available and possible input strings but only a fixed number of out-
puts, collisions must exist for a hash function - our
objective is to ensure that it is computationally in-
Matt Rob&w is a senior research scientist at RSA Laboratories.
feasible to find such examples. The term collision-
He can be contacted at mutt@rsa.com
Page 2
Previous Page Home Next Page
RSA LABORATORIES BULl.ETtN #4 - NOVEMBER 12, 1996




resistant hush function [18] is sometimes used to de- commonly appealed to in a hash function is that of
scribe a hash function that possesses all three of the providing a random looking output. A function
properties described here and it is what most people with this property has many applications and while
have in mind when talking about hash functions in work on collisions for the hash function clearly has
general. implications for any assumptions about its ideal be-
havior, it is not clear that they will necessarily offer
Note that while a collision-resistant hash function a substantial practical reason to move away from
has many useful properties, the property that is actu- that hash function as a matter of urgency. Another
ally appealed to within some application can vary property that might well be largely unaffected by
dramatically. work on collisions is that of being one-way. When
a hash function is being used purely as a one-way
For instance, a hash function is often used to reduce function, perhaps to store a table of hashes of com-
some message to a short string which is then signed puter passwords, then work on collisions might well
with a digital signature algorithm. There is a well- have little relevance.
known attack on this procedure [26] that depends on
the so-called birthday paradox. To prevent this at- In short there are many situations where hash func-
tack we require the property of collision-resistance tions are used for properties other than being colli-
and as a consequence hash functions that produce an sion-resistant and we observe that properties that are
output of at least 128 bits in length. It is worth men- relevant to cryptographic security in one environ-
tioning that this style of attack is more applicable ment are not necessarily relevant in another.
when the digital signature is computed directly on
3. Hash Function Structure
the digest of the message being signed. Newly pro-
posed probabilistic signature schemes by Bellare and Most hash functions have a similar iterative struc-
Rogaway [3] have some very attractive properties and ture which is based around what is termed a com-
pression function [4, 141. In short, the computation
it appears that the requirements we place on a hash
function in such schemes might be less demanding™. of the hash value for some message depends on what
is called a chaining uuriable. At the start of hashing,
Interestingly, digital signatures previously signed us- this chaining variable has a fixed initial value which
ing a hash function that is no longer collision resis- is specified as part of the algorithm. The compres-
tant are likely to remain safe from compromise. In sion function is then used to update the value of
attacking existing signatures, the task of the this chaining variable in a suitably complex way un-
cryptanalyst is essentially that of finding a second der the action and influence of part of the message
preimage since the first preimage (the message signed) being hashed. This process continues recursively,
and the associated hash value are already fixed. This with the chaining variable being updated under the
is a much harder problem than that of generally find- action of different parts of the message, until all the
ing a collision and it might well be the case that tech- message (and any additional padding specified by
niques that generate collisions for a hash function of- the algorithm) has been used. The final value of the
fer no advantage in finding a second preimage. Thus, chaining variable is then output as the hash value
existing signatures might well remain free from risk of corresponding to that message.
compromise even when collision-resistance is lost.
The hash functions MD4 and MD5 are quite similar
in design and, as we have already mentioned, they
When a hash function is used for properties other
were the inspiration behind the design of several
than being collision-resistant, the situation with re-
more recent hash functions. MD2 was an earlier hash
gards to the suitability of that hash function after
the discovery of collisions might remain essentially function with a different structure but it is still widely
used if only because it is suitable for 8-bit environ-
unchanged. Perhaps one of the properties most
ments (unlike MD4 and MD5 which are aimed at
32-bit architectures). In the following sections, we
™ In particular, certain simpk variants of the schemes in [31 might
still securely allow the use of a hash function even though that hash will review the status of the three hash functions
function might not be fully collision-resistant. (These variants would MD2, MD4 and MD5. This note might be viewed as
only differ from the detailed specifications in [31 in the u&r in
an update to the RSA Technical Report TR- 10 1 [22]
which the random number r and the message M are concatenated
which provides an overview of the same hash func-
prior to hashing.) Further work may well reveal other advantages in
tions prior to the very latest developments.
varying the length, or the means of generation, of the value r
Page 3
Previous Page Home Next Page
RSA LABORATORIES B U L L E T I N #4 - N O V E M B E R 12, 1996


. 1
( 19 .)



>>