Subject: New hash algorithms

From: "Bob Jueneman" <[email-masked]>
Date: Tue, 12 Sep 2000 14:20:00 -0600

Rich,

So far, I don't know anything at all about the new hash algorithms
other than what Bill Burr posted.  It does seem like a good idea to 
have a selection of longer hashes available for high value transactions,
though.

According to the Birthday Problem in statistics. two duplicate hash values
could conceivably be found (50% probability of one pair of duplicate)s by 
comparing 2^64 trial values.

Now computing hashes 2^64 is getting close to being feasible -- obviously 
2^56 is feasible since DES has been broken by exhaustive search, and 
a hash algorithm is not as computationally intensive as DES.

Based solely on the computational intensive argument, it would appear that
even SHA-1, which would require 2^80 trials to have a 50% chance of 
success, might not be strong enough, at least in the relatively near future.

But there is some good news, and some bad news.

The bad news is that some attackers might be willing to settle for a lot less 
than a 50% probability of success -- maybe 1%, or even .01% would be 
considered economically viable.  So that would argue that we should 
be conservative with respect to the length of a hash.

The good news, however, is that although the use of massively parallel 
computers with millions of dedicated chips may make the computation of all
of those hashes feasible, there is still the problem of finding a match --
a needle in a million haystacks.

At least with relatively conventional approaches to the problem, the 
sorting and searching problem is probably going to be the upper limit of
feasibility, and not the computational complexity.  

Simply storing the 20 byte result of 2^64 SHA-1 hashes would require
368,934 terabytes of storage -- a very impressive amount.  And SORTING
such a database would be daunting, to say the least.

I'll let the mathematicians who have looked at the problem much more 
recently than I have comment about the best way to find two duplicate 
values somewhere in such a massive amount of data, but when I examined 
that problem several decades ago, I concluded that sorting/searching more
than about 2^40 values was not likely to be feasible.

Since then, however, various techniques ranging from molecular biology
to quantum computers have been proposed, so looking at longer hash 
sizes is probably prudent.

Ideally, the point we would like to get to is where the number of possible 
values to be examined exceeds the estimated number of atoms in the universe,
and/or that the amount of energy needed to cycle through all of those 
states exceeds the amount of energy in the universe. Then we can 
probably quit!

But the original question had to do with whether the hash algorithm 
should be specified independently of the signature algorithm.  For maximum 
flexibility, that would be the desired approach.

I guess what I am saying is that maximum flexibility is NOT what is needed,
because the interoperability and testing complexity (already quite difficult enough)
would rapidly go completely out of sight.

What we need are a SMALL number of judicious choices as to various 
combinations, which each new combination, per se, having to be justified 
on the merits.

Picking winners isn't politically correct, and isn't very popular when every 
contributor has the freedom to push his own pet rock.  But if we don't start 
exercising the necessary engineering judgement and make the hard choices,
the products are going to be come more and more bloated and difficult to 
test, to the detriment of everyone.

Regards,

Bob

But 

>>> "Rich Ankney" <[email-masked]> 09/11/00 06:24PM >>>
Bob,

The current idea is to have OIDs for SHA-256, SHA-512, and SHA-384
(truncated SHA-512).  At least in X9; your comments (and anone else's)
are appreciated.  I know nothing else about these algorithms except the
following: SHA-x (with x >= 256) is not backward with SHA-1, i.e. you
can't truncate a SHA-256 or whatever to SHA-160-bits.  So they are
not doing the obvious (SHA-Y with Y > X in SHA-X being some sort of
iteration of the same function with different IVs).  Of course that's
obviously
only 160 bits strong, so never mind.

This is an area where you have lots of expertsise; I'd be interested in your
ideas (remembering the real version will be distributed to X9 in the next
few weeks, and I'll do my best to leak it to PKIX ASAP).

Best,
Rich

-----Original Message-----
From: Bob Jueneman <[email-masked]>
To: [email-masked] <[email-masked]>; [email-masked] 
<[email-masked]>; [email-masked] 
<[email-masked]>
Date: Monday, September 11, 2000 6:31 PM
Subject: TS TOKEN TYPES - Re: CMC issues, TSP hashes -

>In this regard, I was interested to hear on the Federal PKI TWG list that
NIST
>is considering releasing a SHA-256 and SHA-512 hash algorithm.
>
>No new algorithms will be forthcoming -- the only question is whether to
>bundle them with the conventional signature OID, or to separate them out.
>
>Bundling them makes them somewhat harder to change, but on the other hand,
>allowing complete freedom to choose the signing algorithm independently
tends to
>raise issue of N-squared combinations that have to be tested.
>
>Some combinations might not even make technical sense -- for example
200-bit
>elliptic curve DSA with SHA-512, since the hash function wouldn't fit
within the
>signature result.
>
>On balance, and noting the generally poor track record we have in limiting
>combinations of things to stable profiles, I am inclined to continue the
practice of
>specifying the signature algorithm and the hash algorithm as one joint
specification.
>
>Bob
>
>>>> "todd glassey" <[email-masked]> 09/11/00 01:06PM >>>
>Hi all -
>
>----- Original Message -----
>From: "J Adrian Pickering" <[email-masked]>
>To: <[email-masked]>
>Sent: Wednesday, September 06, 2000 7:57 AM
>Subject: Re: CMC issues, TSP hashes
>
>
>> At 11:57 06/09/00 +0200, Avi Gozlan wrote:
>>
>> >- Use of SHA1 is hard coded in section 5.2. This does not leave the
>> >standard open for other hash algorithms. Are there any plans to change
>> >this?
>>
>> This is a problem shared with the TSP Draft also.
>>
>> (see posting -
>> Date: Sat, 02 Sep 2000 17:37:43 +0100
>> From: J Adrian Pickering <[email-masked]>
>> Subject: TSP Draft - hash enforcement &c
>> which is rather lost amongst the OCSP debate!)
>>
>> Please can something be done about this for everyone's benefit? My
>> suggestion is to introduce a PKIX globally available OID
>> HashAlgorithmIdentifier which is distinct from AlgorithmIdentifier. This
>> will enable other hashes to be used where required/wanted. The
overloading
>> of the AlgorithmIdentifier allows for a parameter which I'm not sure is
>any
>> use in the hash arena?
>
>Actually Adrian  your right - but I think we need a little more than this.
>We need an official PKIX OID Tree and it needs to be available.
>
>For each complex data structure or process that can be uniquely identified
>and that would want to be identified, PKIX needs an OID entry in some PKIX
>master OID Table. Hash's, techniques, and maybe even the IOTP Transaction
>types or something like that as well.
>
>>
>> Russ Housley appears to agree: "The selected one-way hash function must
be
>> uniquely identified by an OID."
>>
>> I'd still rather have the TSA autonomously stamp an octet string and
leave
>> the client to decide what it all means.
>
>We are confusing the term "Client" here for the term "USER OF"... and this
>is an important concept in understanding what we are really talking about.
>
>The key issue is whether the time stamp is used to control some other
>external process, almost analogous to dropping a coin into a vending
>machine,
>or whether it is standing as evidentiary testimony to some event. As it
>happens the Coin does both, but generally the mindset about how the TSP has
>been thought about is form using time as a control parameter rather than an
>evidentiary one. By the way - We generally as a group seem to assume
>automatically between 'using data elements for control' rather than  'for
>content'.
>
>In one case they are used to control the infrastructure or policy
>like a signal, and on the other they are used to stand audit. The uses of
>the same parametric data elements here are very different and have
different
>needs to support their respective end use models.
>
>> What business is it of the TSA to
>> know what it is stamping (semantically or syntactically)?
>
>Depends on what the purpose of the TSA is. If there is a conveyance in a
>legal sense of Agency, then the TSA may have legally binding reasons for
>being able to identify the type of content it is stamping. Maybe to the
>granularity of needing to parse the file first to determine its data type.
>
>.. and this leads us to the fact that a HASH in and of itself as a
>timestamping record is very difficult to use from an end user model. What
>the TST should be is a framework or harness itself and internally it should
>represent a number of events interchangeably. There would need to be
>different grades of Tokens with varying levels of overhead for their
>management, and the approriate BCP to match.
>
>But realize that in no uncertain terms what we are sitting on is  the
>designing of the Global Mint here.
>
>"The real end user goal is a simple bolt-on system that allows end users
to,
>with the transaction infrastructure they have today,  add non-repudiation
>at a commercial level to their process, and  at a scaleable and reasonable
>overhead."
>
>Simple to say, not so simple to do as there are so many different
>transaction
>processing systems in the world today, but the common elements in all of
>them is that they have some DB system that they are layered on and an OS
>under that of some sort.
>
>With that being the key the DB that is, doesn't the idea of a common binary
>data structure that is a timestamp token appeal to you (represented in the
>cyber world as ASN.1 if you want) . We can build an TST Binary to XML
>presentation system and absorb or bridge the IOTP/XML Receipt efforts at
>some level into the PKIX Timestamping systems  and deliver evidentiary
grade
>standards for representing events in time and space. YOW - look at the
>potential
>there!!!.
>
>These tokens and their respective API's will be able to specify its level
of
>trust, the event it marks and the data components that make up that event,
>and the rules of processing the token. If a lighter token is necessary
>portions of the system can be replaced by OIDS on as "as many as possible"
>basis based in the OID tree idea (see above). More risk mitigated
>transactions may require self authenticating tokens as well and we should
>provide for these at the high end of the API.
>
>Poof - Instant transaction systems. I think that this is what DigiCash and
>most all of the other token based transactor companies tried to do but they
>were too far ahead of the curve to get real traction - and as scary as it
>sounds, PKIX is in the perfect position to make this fly now.
>
>BTW, in and of itself is reason for not advancing the TPS Draft.
>
>>
>> Adrian Pickering/
>> Electronics and Computer Science
>> University of Southampton
>> UK
>>
>>
>
>

---

From: "Jeff Davis" <[email-masked]>
Date: Wed, 13 Sep 2000 12:06:02 +0100

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

----- Original Message -----
From: Bob Jueneman <[email-masked]>
To: <[email-masked]>; <[email-masked]>; <[email-masked]>;
<[email-masked]>
Sent: Tuesday, September 12, 2000 9:20 PM
Subject: New hash algorithms

> >>>> "todd glassey" <[email-masked]> 09/11/00 01:06PM
>>>
> >Hi all -
> >