ñòð. 1 |

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 |