Re: Question about Shamir secret sharing scheme

2009-10-04 Thread Hal Finney
Kevin W. Wall asks about Shamir sharing:
 The question that a colleague and I have is there any cryptographic
 purpose of computing the independent coefficients over the finite
 field, Zp ?

Yes, you do have to be careful to do that. You want to make sure the
shares don't leak any information about the secret S.

Consider the simplest case where two people are involved. Call the single
random coefficient c, with secret S, then the two shares are:

S + c
S + 2c

Now if this is mod p, and c is chosen at random mod p, then both c and
2c will be random mod p, and each perfectly hides the value of S when
it is added mod p, similarly to a one-time-pad. Neither share leaks any
information about the value of S.

But suppose for convenience you did the math mod some power of 2 (or
even just over the integers). Then 2c is going to be even, regardless
of c. And seeing S + 2c will then reveal whether S is even or odd,
defeating the privacy of the scheme.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: AES-GMAC as a hash

2009-09-04 Thread Hal Finney
Darren J Moffat asks:
 Ignoring performance for now what is the consensus on the suitabilty of 
 using AES-GMAC not as MAC but as a hash ?

 Would it be safe ?

 The key input to AES-GMAC would be something well known to the data 
 and/or software.

No, I don't think this would work. In general, giving a MAC a fixed key
cannot be expected to produce a good hash. With AES-GMAC in particular,
it is unusual in that it has a third input (besides key and data to MAC),
an IV, which makes your well-known-key strategy problematic. And even as a
MAC, it is very important that a given key/IV pair never be reused. Fixing
a value for the key and perhaps IV would defeat this provision.

But even ignoring all that, GMAC amounts to a linear combination of
the text blocks - they are the coefficients of a polynomial. The reason
you can get away with it in GMAC is because the polynomial variable is
secret, it is based on the key. So you don't know how things are being
combined. But with a known key and IV, there would be no security at all.
It would be linear like a CRC.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Small-key DSA variant

2009-08-25 Thread Hal Finney
While thinking about Zooko's problem with needing small keys, I seem to
have recalled an idea for a DSA variant that uses small keys. I can't
remember where I heard it, maybe at a Crypto rump session. I wonder if
anyone recognizes it.

Let the DSA public key be y = g^x mod p. DSA signatures are defined by:

r = g^k mod p mod q
s satisfies sk - rx = h mod q

Let's define R = g^k mod p. Then r = R mod q. The verification raises
both sides of the s equation to the g power:

g^(sk) / g^(rx) = g^h mod p, or equivalently:
R^s / y^r = g^h mod p

The old ElGamal signature would have been (R,s) (and maybe wouldn't have
used a subgroup). Then this second equation would be the verification
(substituting R for r in the y exponentiation works because the exponent
arithmetic is implicitly mod q). But DSA improved this by using (r,s)
which is smaller. We can't substitute r for R globally in the verification
equation, it won't work. But we can solve for R:

R = g^(h/s) * y^(r/s) mod p

and take this mod q:

r = R mod q = g^(h/s) * y^(r/s) mod p mod q

which is the conventional DSA verification equation.

The small-key variant I'm asking about goes back to the ElGamal
verification equation:

R^s / y^r = g^h mod p

but instead of solving for R, we solve for y in a similar way:

y = R^(s/r) / g^(h/r) mod p

This means that with an ElGamal style (R,s) signature, the verifier
can derive y = g^x mod p. So he doesn't have to know the public key.
Instead of letting the public key be y, we can make it H(y) for some
hash function H. Then the verification is:

H(y) = H( R^(s/r) / g^(h/r) mod p )

We have increased the signature size from twice the size of q to the
sum of the sizes of p and q (which is much bigger, for typical non-EC
DSA groups). But we have decreased the public key from the size of p to
the size of H.

Now the interesting question is whether H can be the size of the security
parameter, rather than twice the size like q. Maybe we could use an 80
bit H. This would make for a very small public key (again at the expense
of a much larger signature).

The idea would be that y is a fixed target, and a forger needs to come
up with an R,s whose hash matches the hash of y. It's a second preimage
problem, not a collision problem.

One issue is that there are many keys in the world, and perhaps a forger
is happy to forge anyone's signature. (Or more to the point, a verifier
really wants to trust all signatures out there.) Then the forger only
needs to match one of H(y) for any of potentially millions or billions
of y values, and this reduces his work by a factor equal to the number of
keys. So we probably do have to boost the key size up to accommodate this
issue. But it could still probably be smaller than for even ECDSA keys.

Anyway, that's the concept. Does anyone recognize it?

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: Certainty

2009-08-25 Thread Hal Finney
Paul Hoffman wrote:
 Getting a straight answer on whether or not the recent preimage work
 is actually related to the earlier collision work would be useful.

I am not clueful enough about this work to give an authoritative answer.
My impression is that they use some of the same general techniques and
weaknesses, for example the ability to make modifications to message
words and compensate them with modifications to other message words
that cancel. However I think there are differences as well, the preimage
work often uses meet in the middle techniques which I don't think apply
to collisions.

There was an amusing demo at the rump session though of a different
kind of preimage technique which does depend directly on collisions. It
uses the Merkle-Damgard structure of MD5 and creates lots of blocks that
collide (possibly with different prefixes, I didn't look at it closely).
Then they were able to show a second preimage attack on a chosen message.

That is, they could create a message and have a signer sign it using MD5.
Then they could create more messages at will that had the same MD5 hash.
In this demo, the messages started with text that said, Dear so-and-so
and then had more readable text, followed by binary data. They were able
to change the person's name in the first line to that of a volunteer
from the audience, then modify the binary data and create a new version
of the message with the same MD5 hash, in just a second or two! Very
amusing demo.

Google for trojan message attack to find details, or read:
slides (not too informative):

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Ultimate limits to computation

2009-08-12 Thread Hal Finney
[Note subject line change]
Jerry Leichter writes:

 Since people do keep bringing up Moore's Law in an attempt to justify  
 larger keys our systems stronger than cryptography, it's worth  
 keeping in mind that we are approaching fairly deep physical limits.   
 I wrote about this on this list quite a while back.  If current  
 physical theories are even approximately correct, there are limits to  
 how many bit flips (which would encompass all possible binary  
 operations) can occur in a fixed volume of space-time.  You can turn  
 this into a limit based solely on time through the finite speed of  
 light:  A computation that starts at some point and runs for n years  
 can't involve a volume of space more than n light years in radius.   
 (This is grossly optimistic - if you want the results to come back to  
 the point where you entered the problem, the limit is n/2 light years,  
 which has 1/8 the spacial volume).  I made a very approximate guess at  
 how many bit-flips you could get in a time-space volume of a 100 light- 
 year sphere; the answer came out somewhere between 2^128 and 2^256,  
 though much closer to the former.  So physical limits prevent you from  
 doing a brute force scan - in fact, you can't even enumerate all  
 possible keys - in 100 years for key lengths somewhere not much more  
 than 128 bits.

Things may not be quite as favorable as this. Here is a posting I made
to cypherpunks in 2004:

Date: Wed,  4 Aug 2004 11:04:15 -0700 (PDT)
From: (Hal Finney)
Subject: Re: On what the NSA does with its tech

MV writes:
 Yes.  They can't break a 128 bit key.  That's obvious.  (if all the
 atoms in the
 universe were computers... goes the argument).

Not necessarily, if nanotechnology works.  128 bits is big but not
that big.

Eric Drexler, in Nanosystems, section 12.9, predicts that a nanotech
based CPU fitting in a 400 nm cube could run at 1000 MIPS and consume
60 nanowatts, performing 10^16 instructions per second per watt.

Let's design a system to break a 128 bit cipher.  Let's suppose it has
to do 2^10 instructions per test, so this is 2^138 instructions total,
or about 10^41.  Let's let it run for four months, which is 10^7 seconds,
so our necessary processing rate is 10^34 instructions per second.

This means we need 10^34 IPS / 1000 MIPS or 10^25 of Drexler's gigahertz
cubes, call it 10^25 cubic microns or 10^7 cubic meters, a cube about
220 meters on a side.

The system will consume 10^25 * 60 nanowatts or about 6 * 10^17 watts.
Now, that's a lot.  It's four times what the earth receives from the sun.
So we have to build a disk four times the area (not volume) of the earth,
collect that power and funnel it to our computers.  Probably we would
scatter the computers throughout the disk, which would be mostly composed
of solar collectors.  (Keeping the disk gravitationally stable is left
as an exercise for the student, as is the tradeoff involved in making
it smaller but moving it closer to the sun.)

Fortunately, exhaustive key search is perfectly parallelizable so there
is no need for complex communications or synchronizations between the

As you can see, breaking 128 bit keys is certainly not a task which is
so impossible that it would fail even if every atom were a computer.
If we really needed to do it, it's not outside the realm of possibility
that it could be accomplished within 50 years, using nanotech and robotics
to move and reassemble asteroids into the necessary disk.

Now, 256 bit keys really are impossible, unless the whole contraption
above can be made to operate as an enormous, unified quantum computer,
in which case it could theoretically break even 256 bit keys.

512 bit keys... now those really are impossible.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Zooko's semi-private keys

2009-07-21 Thread Hal Finney
Zooko's proposal for semi-private keys is worthy of discussion here
I think.  The full idea is in but I
will present it here for your enjoyment (I should emphasize that I played
no part in any of the development of this idea, I just read his PDF).
Apologies in advance for any misunderstandings or misrepresentations I
make. I also want to apologize for using the term secret key rather
than Zooko's preferred private key so that we can call it SK and
then the public key is PK.  The semi-private key will be SPK. Below,
^ refers to repeated iteration of the group operation, in a given group.

With most public key systems, knowing the SK allows you to deduce the PK,
but of course you can't go the other direction:

PK /- SK

Zooko wishes to introduce an intermediate data structure, the semi-private
key or SPK, which fits in between:


From the SK you can deduce the SPK, and from the SPK the PK, but you can't
go backwards.

The reason for this is he wants to issue signatures with the SK which can
be verified by people holding the SPK and by (different) people holding
the PK; and further he wants to be able to create an encryption key from
the SPK, which will (therefore) also be known to the holder of the SK,
but not to holders of the PK. In this way the holder of an SK can have
two groups of verifiers: PK holders can check signatures but not read
data, while SPK holders can both check signatures and read data.

The part that makes this interesting is that it is desired that all of
SK, SPK and PK are as small as possible for a given security level. This
is because of the goal in the Tahoe object-capability distributed file
system of using these keys as identifiers for files. There would be 3
different identifiers for a file in this system, corresponding to the
SK, SPK and PK associated with that file, and each identifier would give
the different levels of cryptographic access described above.

If we didn't have this requirement, we could solve it trivially by
augmenting the SK with an ordinary encryption key k, and defining SPK
as (PK,k). Then the information arrows above would be met. But we have
increased the SK and SPK key sizes by the size of k, which may be a very
substantial percentage when we are dealing with EC keys.

Zooko proposes a specific alternative in his paper, a modification of DSA
(equivalently, ECDSA). In ordinary DSA, SK is a secret exponent x in some
group, and PK is g^x for some generator g of the group. Zooko defines:

y = H(g^x) using hash function H

and proposes that:

SK is xy
SPK is g^x
PK is g^(xy)

It is easy to see that this satisfies the information arrows SK - SPK -
PK. There are no obvious ways to go the other way, but analysis is needed
to verify that. As far as key size, neither SK nor PK gets any bigger,
and SPK is the same size as PK.

DSA signatures are then done in the usual way, using xy in place of
the usual secret exponent x. For reference, and slightly simplified,
the usual DSA formulas are:

r = g^k for some random k;
s is derived from sk * rx = h (mod the group order)

where h is the message hash. Then Zooko's modification merely replaces
x by xy (keep in mind that sometimes y is defined as the public key g^x
in DSA descriptions, but here y is different, y = H(g^x)):

r = g^k for some random k;
s is derived from sk * rxy = h (mod the group order)

Zooko asks for cryptographic community review of this proposal. I believe
I can sketch a couple of simple proofs in the random oracle model that
being able to forge signatures, knowing either SK or SPK, would allow
forging ordinary DSA. This message is getting pretty long though, so
perhaps others will wish to chime in.

The remaining questions are whether PK /= SPK holds, and SPK /= SK.
The second part is easily shown to reduce to discrete log. Suppose we
have an oracle which, given g^x, produces x*H(g^x). Then we can just
divide by H(g^x) and get x, turning it into a discrete log oracle.

The first is equivalent to: knowing g^(xy) is it impossible to deduce g^x,
where y = H(g^x). Define Y = g^x, then y = H(Y) and g^(xy) = Y^H(Y). The
question is then:

Given Y^H(Y) can we deduce Y?

Ideally we'd like to show that an oracle that could solve this could
be used to find arbitrary discrete logs or break some other standard
assumption, but I can't see how to do it. (I also can't see how to go the
other way, from a discrete log oracle to something that can solve this -
seems like a hard problem.)

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: MD6 withdrawn from SHA-3 competition

2009-07-05 Thread Hal Finney
   Thus, while MD6 appears to be a robust and secure cryptographic
   hash algorithm, and has much merit for multi-core processors,
   our inability to provide a proof of security for a
   reduced-round (and possibly tweaked) version of MD6 against
   differential attacks suggests that MD6 is not ready for
   consideration for the next SHA-3 round.

But how many other hash function candidates would also be excluded if
such a stringent criterion were applied? Or turning it around, if NIST
demanded a proof of immunity to differential attacks as Rivest proposed,
how many candidates have offered such a proof, in variants fast enough
to beat SHA-2?

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: SHA-1 in 2**52

2009-06-16 Thread Hal Finney
 Differential Path for SHA-1 with complexity O(2**52)
 Cameron McDonald, Philip Hawkes, and Josef Pieprzyk
 Macquarie University

I wonder now with this new improved differential path if any distributed
computations may be forming to finally create a SHA-1 collision? (I have
a small side bet resting on the outcome...)

I checked this morning, a distributed SHA-1
collision search whichhad been going on since 2007 based on a method
with an estimated cost of 2^60+. However I see that the project page
announces that the effort has been suspended as of May 12, 2009 due
to lack of progress. I wonder if the suspension may also be related to
this new method, reports of which had begun to leak out by that time.

2^52 work should lower the bar substantially, although it would still
be a major task for a single organization. It would be great if the
authors of the improved path could be the ones to announce a collision,
but it sounds like they are more theoretically than practically oriented:

We believe that practical collisions are now within reach of a dedicated
system. We are continuing our search for more differential paths with
a maximum number of auxiliary paths.

(Rather than, we are abandoning our search for more differential paths
and working to try to find a real collision using this one. ;)

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: Popular explanation of fully homomorphic encryption wanted

2009-06-16 Thread Hal Finney
Udhay Shankar N quotes wikipedia:
 The question was finally resolved in 2009 with the development of the
 first true fully homomorphic cryptosystem. The scheme, constructed by
 Craig Gentry, employs lattice based encryption and allows evaluation
 of both addition and multiplication operations without restriction.[2]

2. ^ Craig Gentry. On homomorphic encryption over circuits of
   arbitrary depth. In the 41st ACM Symposium on Theory of Computing
   (STOC), 2009. 

A URL for this paper is but you will have
to be an ACM member to download it. I was able to get a copy this morning
and quickly skimmed it.

This is IMO one of the most remarkable crypto papers ever. Not only
does it solve one of the oldest open problems in cryptography, the
construction of a fully homomorphic encryption system, it does so by
means of a self-embedding technique reminiscent of Godel's theorem.

Craig Gentry starts off by inventing a limited homomorphic encryption
system based on lattice encryption. For full homomorphism you want to do
both add and multiply - or expressed on bits, XOR and AND.  Think of your
operation as a circuit made up of XOR and AND gates, then the limiting
factor in previous work has been the number of ANDs.  While many schemes
have been found that do just XORs, and at least one that could do a very
limited number of ANDs, the new scheme allows you to go deeper.

In lattice encryption, there is a multi-dimensional lattice of points
that have a hidden structure. Encryption puts you near a point on
the lattice, and decryption involves finding that point. But without
knowing the hidden structure, attackers can't tell which one is closest.
In the new homomorphic lattice encryption, AND operations cause the
error term to increase. After too many of them, too deep a circuit,
the error term grows up to roughly half the distance between lattice
points, and decryption is no longer possible. So you have a limited
depth homomorphic encryption system.

By itself this is a substantial advance. But now for the amazing
Godelian trick. The error term has grown and any more operations will
make decryption impossible. So Craig Gentry proposes to allow the server
(which is working on data encrypted under a key controlled by the client)
to decrypt the data - *homomorphically*. If the data is encrypted by
client key pk1, the client has also supplied the server a second key pk2,
and also a version of the pk1 *secret key* encrypted under pk2. Since
pk2 is homomorphic, the server can compute a circuit using the encrypted
secret pk1 key just like it can compute any other circuit on encrypted
data. The result is that the server ends up with an encryption of the
original ciphertext under pk2 instead of under pk1, and because lattice
decryption in effect performs error correction, the error term is reduced
and we are ready for more.

The key idea here is that the homomorphic encryption system has to
allow enough homomorphic depth that *its own decryption algorithm*
can be expressed as a circuit that fits within what can be handled
homomorphically. This is quite difficult and most of the paper is taken
up with constructing such a cryptosystem and proving its properties.
The resulting scheme is apparently not practical (at one point he
mentions that the secret key bits have to be expressed in *unary*) but
it is still amazing that it is even possible. Again I have to go back
to Godel's and Turing's work to think of a comparable example exploiting
the power of self-embedding.

In its most basic form, then, the client must supply a set of public keys
pk1, pk2, ... with each key's private part encrypted under the next key;
the number of such keys would be proportional to the depth of the circuit
to be evaluated. However the paper then points out that given reasonable
assumptions, you can dispense with the whole set and make it a loop,
even a loop of one: that is, you encrypt pk1's private key under pk1,
and stick with pk1 through the whole encryption, including the magical
homomorphic decryption circuit evaluation. In this form it is the pure,
fully homomorphic encryption system which has been so long sought.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: Shamir secret sharing and information theoretic security

2009-02-23 Thread Hal Finney
 Is it possible that the amount of information that the knowledge of a
 sub-threshold number of Shamir fragments leaks in finite precision setting
 depends on the finite precision implementation?

 For example, if you know 2 of a 3 of 5 splitting and you also know that
 the finite precision setting in which the fragments will be used is IEEE
 32-bit floating point or GNU bignum can you narrow down the search for the
 key relative to knowing no fragments and nothing about the finite
 precision implementation?

No, not really. Think of this simple example.

We will have two shares, x and y. Let's work mod 10 to make it simple. The
secret value v will be x + y mod 10. The shares are created by choosing a
random value for x, and then setting y to be v - x mod 10.

So for example if you want to share v = 5, and x is 9, then y will be 6:
9 + 6 = 5 mod 10.

Suppose that you happen to know from other information that the secret
value v is either 1 or 2. Now you learn a share value x = 5. How much
have you learned about v?

Nothing: you can deduce that y is either 6 or 7, but you have no way
of knowing which.  Whatever x had turned out to be, there would be a y
value corresponding to each possible v value. Learning a share tells you
nothing about v, and in general Shamir sharing, learning all but one of
the needed shares similarly tells you nothing about the secret.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: Proof of Work - atmospheric carbon

2009-01-28 Thread Hal Finney
 certificate of validity.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: Bitcoin v0.1 released

2009-01-24 Thread Hal Finney
Jonathan Thornburg writes:
 In the modern world, no major government wants to allow untracable
 international financial transactions above some fairly modest size
 thresholds.  (The usual catch-phrases are things like laundering
 drug money, tax evasion, and/or financing terrorist groups.)
 To this end, electronic financial transactions are currently monitored
 by various governments  their agencies, and any but the smallest of
 transactions now come with various ID requirements for the humans
 on each end.

 But if each machine in a million-node botnet sends 10 cents to a
 randomly chosen machine in another botnet on the other side of the
 world, you've just moved $100K, in a way that seems very hard to
 trace.  To me, this means that no major government is likely to allow
 Bitcoin in its present form to operate on a large scale.

Certainly a valid point, and one which has been widely discussed in
the debates over the years about electronic cash. Bitcoin has a couple
of things going for it: one is that it is distributed, with no single
point of failure, no mint, no company with officers that can be
subpoenaed and arrested and shut down. It is more like a P2P network,
and as we have seen, despite degrees of at least governmental distaste,
those are still around.

Bitcoin could also conceivably operate in a less anonymous mode, with
transfers being linked to individuals, rather than single-use keys. It
would still be useful to have a large scale, decentralized electronic
payment system.

It also might be possible to refactor and restructure Bitcoin to separate
out the key new idea, a decentralized, global, irreversible transaction
database. Such a functionality might be useful for other purposes. Once
it exists, using it to record monetary transfers would be a sort of side
effect and might be harder to shut down.

 I also worry about other domestic ways nasty people could exploit
 a widespread Bitcoin deployment:
 * Spammer botnets could burn through pay-per-send email filters
   trivially (as usual, the costs would fall on people other than the
   botnet herders  spammers).
 * If each machine in a botnet sends 1 cent to a herder, that can add
   up to a significant amount of money.  In other words, Bitcoin would
   make botnet herding and the assorted malware industry even more
   profitable than it already is.

It's important to understand that the proof-of-work (POW) aspect of
Bitcoin is primarily oriented around ensuring the soundness of the
historical transaction database. Each Bitcoin data block records a set
of transactions, and includes a hash collision. Subsequent data blocks
have their own transactions, their own collisions, and also chain to
all earlier hashes.  The result is that once a block is buried under
enough new blocks, it is essentially certain (given the threat model,
namely that attackers cannot muster more than X% of the compute power
of legitimate node operators) that old transactions can't be reversed.

Creating new coins is indeed currently also being done by POW, but I
think that is seen as a temporary expedient, and in fact the current
software phases that out over several years. Hence worries about botnets
being able to manufacture large quantities of POW tokens are only a
temporary concern, in the context of Bitcoin.

There have been a number of discussions in the past about POW tokens as
anti spam measures, given the botnet threat. References are available from
Proof-of-work system on Wikipedia. Analyses have yielded mixed results,
depending on the assumptions and system design.

If POW tokens do become useful, and especially if they become money,
machines will no longer sit idle. Users will expect their computers to
be earning them money (assuming the reward is greater than the cost to
operate). A computer whose earnings are being stolen by a botnet will
be more noticeable to its owner than is the case today, hence we might
expect that in that world, users will work harder to maintain their
computers and clean them of botnet infestations.

Countermeasures by botnet operators would include moderating their take,
perhaps only stealing 10% of the productive capacity of invaded computers,
so that their owners would be unlikely to notice. This kind of thinking
quickly degenerates into unreliable speculation, but it points out the
difficulties of analyzing the full ramifications of a world where POW
tokens are valuble.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: Bitcoin v0.1 released

2009-01-11 Thread Hal Finney
Satoshi Nakamoto writes:
 Announcing the first release of Bitcoin, a new electronic cash
 system that uses a peer-to-peer network to prevent double-spending.
 It's completely decentralized with no server or central authority.

 See for screenshots.

 Download link:

Congratulations to Satoshi on this first alpha release.  I am looking
forward to trying it out.

 Total circulation will be 21,000,000 coins.  It'll be distributed
 to network nodes when they make blocks, with the amount cut in half
 every 4 years.

 first 4 years: 10,500,000 coins
 next 4 years: 5,250,000 coins
 next 4 years: 2,625,000 coins
 next 4 years: 1,312,500 coins

It's interesting that the system can be configured to only allow a
certain maximum number of coins ever to be generated. I guess the
idea is that the amount of work needed to generate a new coin will
become more difficult as time goes on.

One immediate problem with any new currency is how to value it. Even
ignoring the practical problem that virtually no one will accept it
at first, there is still a difficulty in coming up with a reasonable
argument in favor of a particular non-zero value for the coins.

As an amusing thought experiment, imagine that Bitcoin is successful and
becomes the dominant payment system in use throughout the world.  Then the
total value of the currency should be equal to the total value of all
the wealth in the world. Current estimates of total worldwide household
wealth that I have found range from $100 trillion to $300 trillion. With
20 million coins, that gives each coin a value of about $10 million.

So the possibility of generating coins today with a few cents of compute
time may be quite a good bet, with a payoff of something like 100 million
to 1! Even if the odds of Bitcoin succeeding to this degree are slim,
are they really 100 million to one against? Something to think about...


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: MD5 considered harmful today

2008-12-30 Thread Hal Finney

Key facts:

 - 6 CAs were found still using MD5 in 2008: RapidSSL, FreeSSL, TC
   TrustCenter AG, RSA Data Security, Thawte, Out of the
   30,000 certificates we collected, about 9,000 were signed using MD5,
   and 97% of those were issued by RapidSSL. RapidSSL was used for the

 - The attack relies on cryptographic advances in the state of the art for
   finding MD5 collisions from inputs with different prefixes. These advances
   are not yet being published but will presumably appear in 2009.

 - The collision was found using Arjen Lenstra's PlayStation Lab and used
   200 PS3s with collectively 30 GB of memory. The attack is in two parts,
   a new preliminary birthdaying step which is highly parallelizable and
   required 18 hours on the PS3s, and a second stage which constructs the
   actual collision using 3 MD5 blocks and runs on a single quad core PC,
   taking 3 to 10 hours.

 - The attack depends on guessing precisely the issuing time and serial
   number of the good certificate, so that a colliding rogue
   certificate can be constructed in advance. The time was managed
   by noting that the cert issuing time was reliably 6 seconds after
   the request was sent. The serial number was managed because RapidSSL
   uses serially incrementing serial numbers. They guessed what serial
   number would be in use 3 days hence, and bought enough dummy certs
   just before the real one that hopefully the guessed serial number would
   be hit.

 - The attacks were mounted on the weekend, when cert issuance rates are
   lower. It took 4 weekends before all the timing and guessing worked right.
   The cert was issued November 3, 2008, and the total cert-purchase cost was

 - The rogue cert, which has the basicConstraints CA field set to TRUE, was
   intentionally back-dated to 2004 so even if the private key were stolen,
   it could not be misused.

My take on this is that because the method required advances in
cryptography and sophisticated hardware, it is unlikely that it could
be exploited by attackers before the publication of the method, or
the publication of equivalent improvements by other cryptographers. If
these CAs stop issuing MD5 certs before this time, we will be OK. Once
a CA stops issuing MD5 certs, it cannot be used for the attack. Its old
MD5 certs are safe and there is no danger of future successful attacks
along these lines.  As the paper notes, changing to using random serial
numbers may be an easier short-term fix.

Therefore the highest priority should be for the six bad CAs to change
their procedures, at least start using random serial numbers and move
rapidly to SHA1. As long as this happens before Eurocrypt or whenever
the results end up being published, the danger will have been averted.
This, I think, is the main message that should be communicated from this
important result.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: Bitcoin P2P e-cash paper

2008-11-13 Thread Hal Finney
 this in its

A very good point, and a more complete specification is necessary in order
to understand how the network will respond to imperfections like this. I
am looking forward to seeing more detail emerge.

One thing I might mention is that in many ways bitcoin is two independent
ideas: a way of solving the kinds of problems James lists here, of
creating a globally consistent but decentralized database; and then using
it for a system similar to Wei Dai's b-money (which is referenced in the
paper) but transaction/coin based rather than account based. Solving the
global, massively decentralized database problem is arguably the harder
part, as James emphasizes. The use of proof-of-work as a tool for this
purpose is a novel idea well worth further review IMO.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Bitcoin P2P e-cash paper

2008-11-08 Thread Hal Finney
Bitcoin seems to be a very promising idea. I like the idea of basing
security on the assumption that the CPU power of honest participants
outweighs that of the attacker. It is a very modern notion that exploits
the power of the long tail. When Wikipedia started I never thought it
would work, but it has proven to be a great success for some of the
same reasons.

I also do think that there is potential value in a form of unforgeable
token whose production rate is predictable and can't be influenced
by corrupt parties. This would be more analogous to gold than to fiat
currencies. Nick Szabo wrote many years ago about what he called bit
gold[1] and this could be an implementation of that concept. There have
also been proposals for building light-weight anonymous payment schemes on
top of heavy-weight non-anonymous systems, so Bitcoin could be leveraged
to allow for anonymity even beyond the mechanisms discussed in the paper.

Unfortunately I am having trouble fully understanding the system. The
paper describes key concepts and some data structures, but does not
clearly specify the various rules and verifications that the participants
in the system would have to follow.

In particular I don't understand exactly what verifications P2P nodes
perform when they receive new blocks from other nodes, and how they
handle transactions that have been broadcast to them. For example, it
is mentioned that if a broadcast transaction does not reach all nodes,
it is OK, as it will get into the block chain before long. How does this
happen - what if the node that creates the next block (the first node
to find the hashcash collision) did not hear about the transaction,
and then a few more blocks get added also by nodes that did not hear
about that transaction? Do all the nodes that did hear it keep that
transaction around, hoping to incorporate it into a block once they get
lucky enough to be the one which finds the next collision?

Or for example, what if a node is keeping two or more chains around as
it waits to see which grows fastest, and a block comes in for chain A
which would include a double-spend of a coin that is in chain B? Is that
checked for or not? (This might happen if someone double-spent and two
different sets of nodes heard about the two different transactions with
the same coin.)

This kind of data management, and the rules for handling all the packets
that are flowing around is largely missing from the paper.

I also don't understand exactly how double-spending, or cancelling
transactions, is accomplished by a superior attacker who is able to muster
more computing power than all the honest participants. I see that he can
create new blocks and add them to create the longest chain, but how can
he erase or add old transactions in the chain? As the attacker sends out
his new blocks, aren't there consistency checks which honest nodes can
perform, to make sure that nothing got erased? More explanation of this
attack would be helpful, in order to judge the gains to an attacker from
this, versus simply using his computing power to mint new coins honestly.

As far as the spending transactions, what checks does the recipient of a
coin have to perform? Does she need to go back through the coin's entire
history of transfers, and make sure that every transaction on the list is
indeed linked into the timestamp block chain? Or can she just do the
latest one? Do the timestamp nodes check transactions, making sure that
the previous transaction on a coin is in the chain, thereby enforcing
the rule that all transactions in the chain represent valid coins?

Sorry about all the questions, but as I said this does seem to be a
very promising and original idea, and I am looking forward to seeing
how the concept is further developed. It would be helpful to see a more
process oriented description of the idea, with concrete details of the
data structures for the various objects (coins, blocks, transactions),
the data which is included in messages, and algorithmic descriptions
of the procedures for handling the various events which would occur in
this system. You mentioned that you are working on an implementation,
but I think a more formal, text description of the system would be a
helpful next step.

Hal Finney


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: privacy in public places

2008-08-29 Thread Hal Finney
It is hard to argue with Perry's point that privacy in public is an
endangered species at best. Suggesting that one confine one's illegal
actions to the virtual world is not a particularly appealing response.

Robin Hanson considered the problem in this article from back in the
1990s, a response to the heyday of the Cypherpunks:

He argued that virtual privacy would not be an adequate substitute for
the loss of physical privacy, that people would not be willing to make
the sacrifices necessary for a fully anonymous (or pseudonymous) online

It's possible nevertheless that online substitutes for many questionable
physical activities may arise. People don't need to shop at adult
bookstores any more, porn being widely available online. Instructions on
making or growing your own drugs can also be found. Not everything we do
in the physical world can yet be virtualized but perhaps with increased
recognition of the problem, more substitutes will become available.

You don't have to buy into the Cypherpunk picture of a set of fully
protected nyms using Chaumian credentials to transfer attributes,
in order to benefit still from the relatively large degree of anonymity
and privacy available online.

It may also be helpful to focus more directly on specific harms and
specific limitations rather than the rather vague and general issue of
privacy and its intangible benefits. Scientific American has a number
of articles on this topic in its most recent issue.

(Also includes a nice article by Anna Lysyanskaya on cryptographic
credentials BTW. Her work with Jan Camenisch on this topic remains state
of the art for those who still retain hope for the technology. TPM DAA
is based on CL signatures and ironically may become the first widely
fielded use of anonymous credentials.)

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Decimal encryption

2008-08-28 Thread Hal Finney
I wrote:
 Looking a little more closely, I found this paper by Patarin from
 Crypto 2005 which describes security bounds for higher round Feistel

I was wrong, this was from Crypto 03. And as Eric Rescorla has already
pointed out, Patarin had an improved the result the following year where
he showed that 6 rounds was sufficient for security.

Greg Rose wrote:
  So, you don't have a 133-bit block cipher lying around? No worries, I'll
  sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit
  block cipher like AES. To encrypt, do:
  1. Encrypt the first 128 bits (ECB mode)
  2. Encrypt the last 128 bits (also ECB mode).

 Hal Finney wrote:
  I am not familiar with the security proof here, do you have a reference?
  Or is it an exercise for the student?

 It's a degenerate case of Rivest's All-or-nothing transform (which 
 applies to larger, multi-block blocks, if you know what I mean :-) ). I 
 believe he gave a security proof, some 6ish years ago. But I could be 

Hmmm, looking at Rivest's package transform which was his original
proposal for an AONT, that seems to be different and actually expanded
the message size. I haven't been able to find an AONT which is quite
like this.

One limitation with this proposal is that it appears that it will only
be as strong as the size of the overlapping region. However in this case
the overlap is 128-5 or 123 bits, so the birthday bound will be about
2^62 rather than the ideal 2^64, and that is hardly noticeable. So it
does seem like it could be a good choice here. Doing a little over 3 AES
encryptions will be much better than the 6 which seem to be necessary for
the Feistel approach. However such a substantial improvement certainly
makes a proof of security more interesting.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Decimal encryption

2008-08-27 Thread Hal Finney
Philipp Gühring writes:
 I am searching for symmetric encryption algorithms for decimal strings.

 Let's say we have various 40-digit decimal numbers:

 As far as I calculated, a decimal has the equivalent of about 3,3219
 bits, so with 40 digits, we have about 132,877 bits.

Right, although as an American I was confused for a moment until I
remembered the European convention of using comma for the decimal point,
while we use period. But you are right and it was my mistake.

 Now I would like to encrypt those numbers in a way that the result is a
 decimal number again (that's one of the basic rules of symmetric
 encryption algorithms as far as I remember).

 Since the 132,877 bits is similar to 128 bit encryption (like eg. AES),
 I would like to use an algorithm with a somewhat comparable strength to AES.
 But the problem is that I have 132,877 bits, not 128 bits. And I can't
 cut it off or enhance it, since the result has to be a 40 digit decimal
 number again.

This is a very common question. Unfortunately the state of the art in
cryptography does not as far as I know have a good answer. The most recent
analysis I found is
from CT-RSA 2002 by Black and Rogaway.

Basically they propose what is called a Luby-Rackoff construction,
related to another construction called a Feistel network. Unfortunately
their analysis does not show that this is secure, but I believe that by
adding more steps it can be made so.

The idea is to start with your 40 digit number and split it into two parts
of 20 digits. Call the left part L and the right part R. Then repeatedly
execute the following steps:

L = (L xor AES(R)) mod 10^20
(L,R) = (R,L) (i.e. interchange L and R)

After doing this a certain number of steps, interchange L and R one
last time, and concatenate L and R to get your output. (Equivalently,
skip the interchange of L and R on the last step.)

Now, it is important in doing this that AES have a different key for
each round or step. You can start with a single key K, and generate
the round keys as K0 = AES(K,0), K1 = AES(K,1), K2 = AES(K,2), and so on.

To decrypt, the same basic process is used. But this time, use the round
keys in the reverse order. Instead of K0, K1, K2, use K2, K1, K0.

Black and Rogaway analyzed for just 3 rounds, and they found basically
that for your case, this construction would only have about 32 bits of
strength; that is, after encrypting about 4 billion numbers, you would
be losing security.  If you are only ever encrypting many fewer numbers
than this (with a given key), it should probably be OK.

The other possibility is to increase the number of rounds. The paper
hints that this will help but does not offer any specific analysis. I saw
a speculative comment online that 8 rounds would be strong. I believe
that going back to the Luby-Rackoff paper may offer some guidance,
but I don't have time to do that now.

Note that this unfortunately does not get the benefit you were hoping for
from being so close to the AES block size. While there are some known
tricks for dealing with being a little shorter than the cipher block,
I couldn't find any good ones for being a few bits longer.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Decimal encryption

2008-08-27 Thread Hal Finney
I like Greg Rose's solution best:

 There is a fairly standard technique for handling things like this.

 1. encode your number N into a 133-bit string S
 2. encrypt S with your favourite 133-bit block cipher (see below)
 3. decode S to a number N'
 4. if N' = 10^40, goto 2 (that is, re-encrypt until it is in range)
 5. N' is your answer.

This is Rich Schroeppel's trick from his Hasty Pudding cipher, a somewhat
under-rated AES submission IMO. HPC originated not only this trick,
but also the idea of tweakable encryption, which has turned out to be
important for disk encryption. The Black-Rogaway paper referenced earlier
has a proof of security of this construction.

 So, you don't have a 133-bit block cipher lying around? No worries, I'll 
 sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit 
 block cipher like AES. To encrypt, do:

 1. Encrypt the first 128 bits (ECB mode)
 2. Encrypt the last 128 bits (also ECB mode).

I didn't understand this at first, but I finally saw that the point is to
do the encryptions in-place; step 1 replaces the first 128 bits of the
data with the encryption, and similarly for step 2. This is equivalent
to doing CBC mode with a fixed IV of 0, and ciphertext stealing for the
final partial block of 5 bits.

 To decrypt, do decryptions in the reverse order, obviously. It's easy to 
 see that this is a secure permutation if AES itself is, depending on 
 your definition of secure; if you add a third step, to re-encrypt the 
 first 128 bits, it is truly secure. (Without the third step, tweaking a 
 bit in the first 5 bits will often leave the last 5 unchanged on 
 decryption, which is clearly a distinguishing attack; the third 
 encryption makes it an all-or-nothing transform.)

I am not familiar with the security proof here, do you have a reference?
Or is it an exercise for the student?

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

The MD6 hash function (rough notes)

2008-08-21 Thread Hal Finney
. However Adi Shamir stood up
and expressed concern that his new Cube attack might apply. Rivest seemed
confident that the degree of MD6 would be several thousand, which should
be safe from Shamir's attack, but time will tell.

Apologies again to the enormous number of authors if I have any serious
errors above. And thanks to Ron Rivest for publicizing this hash design
several months before the due date (October 31), potentially giving an
advantage to his competitotrs. He emphasized that his goal is to produce
the best possible outcome for the whole process.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: OpenID/Debian PRNG/DNS Cache poisoning advisory

2008-08-08 Thread Hal Finney
[I feel a little uncomfortable replying with such a wide distribution!]

Getting browsers, or OpenID installations, to check CRLs or use OCSP to
check for freshness is likely to be slow going. At this point I think
the momentum still favors fixing the remaining DNS systems that are
vulnerable to cache poisoning. This turnkey-MITM bug makes OpenSSL bad
certs far more exploitable, as Dan Kaminsky pointed out in his report.
OpenID is just one example of many where this is going to keep happening
as long as DNS is unpatched.

I thought of one possible mitigation that can protect OpenID end users
against remote web sites which have not patched their DNS. OpenID
providers who used weak OpenSSL certs would have to change their URLs
so that their old X.509 CA certs on their old URLs no longer work on the
new ones. This will require all of their clients (users who log in with
their OpenID credentials) to change their identifiers. DNS based MITMs
will not be able to forge messages related to the new identifiers.

Customers can be alerted to this requirement as soon as they log in to
a web site (relying party) whose DNS is NOT hacked; the redirection to
the OpenID provider will give opportunity to notify the customer of the
name change. Making this change may be somewhat inconvenient, but since
OpenID is a relatively new standard, at least it is easier than would
be the case with a more established protocol.

In the other direction of attack, the end user's DNS is poisoned and
he gets redirected to a bogus site in place of the OpenID provider;
that site is then able to provide a valid SSL certificate due to the
OpenSSL weakness, thereby stealing whatever authentication credentials
the user normally sends to his OpenID provider. This is one instance of
the general attack where a user is DNS-misdirected to a bogus copy of
a secure site which unfortunately used weak OpenSSL based certs.

Again, I see fixing the DNS as the path of least resistance here,
especially so since the end user is the one bearing most of the risk,
typically DNS is provided by an ISP or some other agency with a formal
legal relationship, and there is the possibility of liability on the
part of the lax DNS provider. Hopefully we will continue to see rapid
uptake of the DNS fix over the next few weeks.

That still leaves weak-cert OpenID users vulnerable to DNS-unpatched
service providers (OpenID relying parties), and that is where my proposed
mitigation above comes in. By renaming its URLs, an OpenID provider who
had the misfortune to create a weak OpenSSL cert (through no fault of
its own) can save its end users considerable potential grief.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: On the randomness of DNS

2008-07-30 Thread Hal Finney
Ben Laurie writes:
 Oh, and I should say that number of ports and standard deviation are not 
 a GREAT way to test for randomness. For example, the sequence 1000, 
 2000, ..., 27000 has 27 ports and a standard deviation of over 7500, 
 which looks pretty GREAT to me. But not very random.

That's a good point, Ben. Dan Kaminsky's DNS tester at
does include output like this:

Your name server, at, appears to be safe, but make sure the
ports listed below aren't following an obvious pattern (:1001, :1002,
:1003, or :3, :30020, :30100...).
Requests seen for TXID=64660 TXID=51678 TXID=49711 TXID=12263 TXID=59610 

This shows only the last 5 ports so it won't detect an LCG, but at least
it can detect some of the more obvious patterns.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Strength in Complexity?

2008-07-02 Thread Hal Finney
 There are, of course, obstacles that must still be overcome by EKMI 
 proponents. For example, the proposed components are somewhat simple 
 by design, which concerns some encryption purists who prefer more 
 complex protocols, on the logic that they're more difficult to break 

Let me first say that from the discussion here I now get the impression
that this is how criticism of the EKMI spec is being characterized by its
supporters. Their critics are encryption purists. I'm not sure what
that means but it sounds kind of like people who believe in security
over simplicity.

An example where this concern might arise would be an overly simplistic
protocol that used AES in ECB mode - simple by design, while the
encryption purist advocated GCM, more difficult to break into but
more complex.  Now, I'm sure EKMI is not doing things this way but it
is an example where simple would not look good to encryption purists.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: The perils of security tools

2008-05-22 Thread Hal Finney
Ben Laurie alerts us to the recent bug in Debian distributions of
OpenSSL which caused the RNG to have almost no entropy. The distribution
mistakenly commented out the call that added seeding and most other
sources of entropy to the RNG state. This is requiring many keys to
be re-issued.

One of the more unfortunate aspects of this bug is that it affects not
only keys generated on systems with the weak RNG, but also even securely
generated DSA keys, if the keys were used for signing on systems with
the bug. DSA keys are vulnerable to weak RNGs not only at keygen time
but at any later time that signatures are created. This causes those
keys to be far more vulnerable to problems in RNGs.

The reason is the DSA signature equation sk - xr = h, where h is the
message hash, r and s are signature components, x is the private key,
and k is a random value chosen uniquely per message. If k is guessable,
as potentially was the case with this recent bug, then x can be deduced
since the other values are typically sent in the clear.

A simple trick can be used to help immunize DSA signatures against
these kinds of failures. I first learned of this idea many years ago
from Phil Zimmermann, and a varient has been used for a long time in
PGP and probably other code, but aparently not OpenSSL. The idea is
to base the random k not just on the output of your RNG, but also on
the private key x. Something like:

k = hash (x, rng()).

Of course it is still necessary that k be uniformly distributed mod q
(the DSA subgroup prime order), so this can't be just a straight hash.
It might be a separate PRNG instance which gets seeded with the data
values shown.  But the idea is to mix in the secret key value, x, in
addition to data from the RNG.

In this way, if the rng data is predictable but the secret key is unknown,
k should still be unguessable. And if your mixing function is good then
this should not leak any information about x, especially in the usual
case where the rng is of good quality.

A variant on this idea protects against a separate problem, where k
is unguessable but somehow the same k value is used for two separate
signatures. This again lets the attacker deduce x because he will observe
two instances of the DSA signature equation above, with all values known
except k and x, and since k is the same, this is two equations with two
unknowns and allows recovering both values.

To immunize against this failure, include the message hash h in the mixing
function that generates k:

k = hash (x, h, rng()).

Now, if the RNG does produce identical output, h will typically differ
among signatures, again producing unique and unguessable k values. And
if h is the same for two messages in this form, k will be the same, but
then r and s will be the same as well, and the second signature will be
an exact match of the first and not leak new information.

I think these techniques are widely known among implementors but I did
not see them in HAC so I thought it was worth reminding the community
here. OpenSSL is such a widely used crypto library that it would be
especially valuable for it to consider incorporating these mechanisms. It
would have saved some considerable pain as administrators who use OpenSSH
(which depends on OpenSSL) DSA keys now are forced to consider whether
they may be vulnerable to the bug even if their primary servers were not
exposed to it, since any client out there may have generated insecure
signatures and inadvertantly revealed secret keys.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: RNG for Padding

2008-03-17 Thread Hal Finney
Mr Pink writes:
 In Applied Crypto, the use of padding for CBC encryption is suggested
 to be met by ending the data block with a 1 and then all 0s to the end
 of the block size.

 Is this not introducing a risk as you are essentially introducing a
 large amount of guessable plaintext into the ciphertext.

 Is it not wiser to use RNG data as the padding, and using some kind of
 embedded packet size header to tell the system what is padding?

Back in 2001, there was a discussion of the general issue of altering data
structures to avoid known plaintext on sci.crypt, under the subject of
Known Plaintext Considered Harmless. A surprising diversity of opinions
were expressed.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: questions on RFC2631 and DH key agreement

2008-02-09 Thread Hal Finney
Jeff Hodges wrote:
 It turns out the supplied default for p is 1024 bit -- I'd previously goofed 
 when using wc on it..


This p is a strong prime, one where (p-1)/2 is also a prime, a good
property for a DH modulus. The generator g=2 generates the entire group,
which is an OK choice. It means that one bit of the shared secret is
leaked (whether or not it is a quadratic residue, i.e. whether the
discrete log of the number is even or odd). But that shouldn't matter,
the shared secret should be hashed and/or used as the seed of a PRNG to
generate further keys.

The main problem as I said is that 1024 bit moduli are no longer
considered sufficiently safe for more than casual purposes. Particularly
with discrete logs that use a widely-shared modulus like the one above,
it would not be surprising to see it publicly broken in the next 5-10
years, or perhaps even sooner. And if a public effort can accomplish it
in a few years, conservatively we should assume that well funded secret
efforts could already succeed today.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: questions on RFC2631 and DH key agreement

2008-02-09 Thread Hal Finney
Jeff Hodges wrote:
 Thanks for your thoughts on this Hal. Quite educational. 

  Jeff Hodges wrote:
   It turns out the supplied default for p is 1024 bit -- I'd previously 
   when using wc on it..
  This p is a strong prime, one where (p-1)/2 is also a prime, a good
  property for a DH modulus.

 Ok, so what tools did you use to ascertain that? I'm curious. 

I copied and pasted it into Python as p, set p1 = (p-1)/2, and did
pow(2L,p1-1,p1), pow(3L,p1-1,p1) and a few such Fermat tests, always
getting 1 as the result, to confirm that p1 is prime. I then did
pow(2L,p1,p) and got p-1 rather than 1, which tells me that 2 generates
the whole group rather than the subgroup of order p1.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: questions on RFC2631 and DH key agreement

2008-02-09 Thread Hal Finney
Hi Jeff -
 How wise (in a real-world sense) is it, in a protocol specification, to 
 specify that one simply obtain an ostensibly random value, and then use that 
 value directly as the signature key in, say, an HMAC-based signature, without 
 any further stipulated checking and/or massaging of the value before such use?

I think it's OK, as long as it is understood that the random number
generator should be of good quality. If it is not, I don't know that
checking and/or massaging will help much.

 E.g., here's such a specfication excerpt and is absolutely everything said in 
 the spec wrt obtaining said signature keys:

   When generating MAC keys, the recommendations in [RFC1750] SHOULD be 

One point, RFC1750 has been superceded by RFC4086.

   The quality of the protection provided by the MAC depends on the randomness 
   the shared MAC key, so it is important that an unguessable value be used.

 How (un)wise is this, in a real-world sense? 

It seems pretty reasonable to me. They are referring to an RFC with
lots of good advice about random number generators, and they emphasize
that the key value should be unguessable. It's probably out of scope to
go into a lot more detail than that. Referring to other standards like
RFC1750/4086 is the right way to handle this kind of issue.

 [yes, I'm aware that using a only a SHOULD here leaves a huge door open 
 compliance-wise, but that's a different issue]

I am the co-author of the OpenPGP Standard, RFC4880. All we say is:

   The sending OpenPGP generates a random number to be used as a
   session key for this message only.


   * Certain operations in this specification involve the use of random
 numbers.  An appropriate entropy source should be used to generate
 these numbers (see [RFC4086]).

Not all that different in thrust than the spec you are looking at.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: questions on RFC2631 and DH key agreement

2008-02-06 Thread Hal Finney
Jeff Hodges writes:
 If a purportedly secure protocol employing a nominal DH exchange in order 
 establish a shared secret key between a requester and responder, employs 
 widely known published (on the web) fixed values for g (2) and p (a 
 purportedly prime 1040 bit number) for many of it's implementations and 
 runtime invocations, what are the risks its designers are assuming with 
 respect to the resultant properties of ZZ?

This can be reasonably safe, if p is chosen properly. There is no problem
with using g=2, with the right p. The main issue is that with current
technology, a 1040 bit p stands a substantial chance of being broken.
A 1024 bit special-form number was factored last year, with claims that
the technique might apply to general RSA moduli of that size. Finding
discrete logs takes similar work.  A widely reused p value would be a
fat target for such an effort.

 I suspect that many implementations will simply use the equivalent of 
 rand() function is available to get the bits for their private keys directly, 
 and will likely not reallocate private keys unless the implementation or 
 machine are restarted. So if the random number generator has known flaws, 
 there may be some predictability in both the public keys and in ZZ, yes? 
 Additionally there's the previously noted issue with the values of static 
 private keys slowly leaking.

I'm not sure about this leaking, I asked Ashwood for clarification.
Certainly if the secret exponents are poorly chosen, the system will be
insecure. I would not necessarily assume that rand() is being used; I
would hope in this day and age that people would know better than that.
/dev/random on LinuxMac and CryptGenRandom on Windows should provide
adequate security for this use, and hopefully the implementors would be
aware of the need for secure random numbers.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: questions on RFC2631 and DH key agreement

2008-02-06 Thread Hal Finney
Joseph Ashwood writes, regarding unauthenticated DH:
 I would actually recommend sending all the public data. This does not take 
 significant additional space and allows more verification to be performed. I 
 would also suggest looking at what exactly the goal is. As written this 
 provides no authentication just privacy, and if b uses the same private key 
 to generate multiple yb the value of b will slowly leak.

I'm not familiar with this last claim, that the value of b's private key
(presuming that is what you mean) would slowly leak if it were reused for
many DH exchanges. Can you explain what you mean? Are you talking about
LimLee style attacks where the recipient does not check the parameters
for validity? In that case I would say the private exponent would leak
quickly rather than slowly. But if the parameters are checked, I don't
see how that would leak a reused exponent.

 You can then use the gpb trio for DSA, leveraging the key set for more 

Presuming here you mean (g,p,q) as suitable for reuse. This raises the
question, is the same set of (g,p,q) parameters suitable for use in both
DH exchange and DSA signatures?

From the security engineering perspective, I'd suggest that the goals and
threat models for encryption vs signatures are different enough that one
would prefer different parameters for the two. For DSA signatures, we'd
like small subgroups, since the subgroup size determines the signature
size. This constraint is not present with DH encryption, where a large
subgroup will work as well as a small one. Large subgroups can then
support larger private exponents in the DH exchange.

Now it may be argued that large subgroups do not actually increase
security in the DH exchange, because index calculus methods are
independent of subgroup size. In fact, parameters for DSA signatures
are typically chosen so that subgroup based methods such as Shanks that
take sqrt(q) cost are balanced against estimates of index calculus
work to break p. However, this balancing is inherently uncertain and
it's possible that p-based attacks will turn out to be harder than ones
based on q. Hence one would prefer to use a larger q to provide a margin
of safety if the costs are not too high. While there is a computational
cost to using a larger subgroup for DH exchange, there is no data cost,
while for DSA there are both computational and data costs. Therefore the
tradeoffs for DH would tend to be different than for DSA, and a larger
q would be preferred for DH, all else equal. In fact it is rather common
in DH parameter sets to use Sophie-Germain primes for q.

We may also consider that breaking encryption keys is a passive
attack which can be mounted over a larger period of time (potentially
providing useful information even years after the keys were retired)
and is largely undetectable; while breaking signatures, to be useful,
must be performed actively, carries risks of detection, and must be
completed within a limited time frame. All these considerations motivate
using larger parameter sets for DH encryption than for DSA signatures.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Possible backdoor in FIPS SP 800-90 PRNG

2007-11-15 Thread Hal Finney
Slashdot this morning has a posting about the possibility of a back door
in the elliptic curve random number generator in FIPS SP 800-90. has links to an
article by Bruce Schneier at, the standard, and the presentation
with the new result.

The work is by Dan Shumow and Niels Ferguson and was presented at the
Crypto 2007 rump session. Basically there are two elliptic curve points,
and if you know the discrete logarithm of one relative to the other,
you can reverse engineer the internal state just from the RNG outputs.
It's a very nice piece of analysis.

The problem is that NIST publishes a pair of points that they suggest you
use, in Appendix A.1, without giving any hint of how they were derived.
This leaves open the possibility that they were selected in such a way
as to exploit the Shumow/Ferguson back door.

Now, here's the strange thing. In Appendix A.2 NIST says that you can use
your own pair of points if you want to. But, they caution very strongly
that in that case, anyone relying on the PRNG should verify that the pair
of points were generated randomly. They describe a specific procedure for
generating random points in a provable way (via hashing some other data)
and require that the seeds that were used be saved and made available
to the verifier.

They don't say anything about why this is important, but the work by
Shumow and Ferguson now makes it clear. Otherwise there is the possibility
of a very serious back door.

So this raises the obvious question, why didn't NIST publish the seeds
that were used to generate the default points from Appendix A.1? It
seems odd that they are so insistent about using a verifiable procedure
to create points, and then they don't say whether they followed it

If they did use that procedure, NIST could simply publish the seeds for
the point generation and everyone will be able to verify that the points
are random and there is no back door.

Unfortunately there is a complication, which is that one of the pair of
points is inherited from FIPS 186-3, the Digital Signature Standard. The
EC PRNG uses the curve and base point from EC DSS. It then chooses another
point, and the two points are used for the PRNG. It's not particularly
likely that the base point from EC DSS was generated via the randomizing
technique prescribed for the EC RNG. And even if the 2nd point for the
EC RNG is in fact generated randomly and they can prove it, it would not
rule out the possibility that the base point from EC DSS had actually
been pre-selected to allow for a back door. It is crucial that both
points be generated randomly for the EC RNG to be secure.

Ironically, the EC DSS standard does publish a seed used for a
PRNG to generate the elliptic curves, so as to assure that they are
random. However based on my reading of IEEE P1363 which tells how to do
this, it does not appear that the seed constrains the base point, only
the curve parameters. Unless NIST did use a verifiably random method to
generate the base points in EC DSS and the 2nd points in EC PRNG then
there is no foundation for security.

Therefore the only reasonable way forward is for NIST to either publish
the seeds that were used for these points, if they exist, or to revise
the standard to use new points and publish the seeds for both of them.
There is no need to re-use the points from FIPS 186-3, a new pair of
points should be chosen for the PRNG via the specified randomization.

Hal Finney
PGP Corporation

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: interesting paper on the economics of security

2007-08-22 Thread Hal Finney
Steven M. Bellovin forwards a pointer to: 

Ross Anderson gave his invited talk at Crypto yesterday on this topic
of the economics of crypto and security. It was an excellent talk,
showcasing a new way to look at problems that sheds light on a number
of otherwise odd behaviors.

At the same time economics is inherently fuzzier than the kind of
mathematical precision we aim for in crypto results. It often seems that
every economic claim has an opposing one with arguments on each side.
Along these lines, I felt that many of the points Ross made were open
to debate and interpretation.

One example was his comparison between the security business and the
used-car lemons market. The idea is that lemons dominate the used-car
market due to asymmetric information: only the sellers know which cars
are lemons, hence these are the ones that are mostly made available,
hence buyers assume all cars are likely to be lemons, hence good cars
can't be sold for a higher price and are largely kept off the market.

However security products are not really that much like used cars. Used
cars are individually unique and it is impossible to know in advance
how well they will work. That's where the asymmetric information
comes from. But security products are more like other retail products;
each one has its own characteristics, strengths and weaknesses, and
there are ways consumers can find out about them in advance. There was
considerable publicity a couple of weeks ago about a side-by-side test
at the LinuxWorld conference which compared ten anti-virus products,
with highly differentiated results:

Information on the quality of AV and other security products is widely
available on the net, in magazines and other places that consumers
might look for reviews and comparisons. This is completely unlike
the situation with individual used cars. I don't see this analogy as
particularly accurate.

I certainly do fully support the concept behind Ross's program of
investigating the role economics plays in the crypto and security field.
The mere fact that so many of the conclusions are provocative indicates
that there is much fertile work yet to be done. Ross is a major pioneer
of this effort and I am looking forward to further interesting results.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: remote-attestation is not required (Re: The bank fraud blame game)

2007-07-03 Thread Hal Finney
Adam Back [EMAIL PROTECTED] writes:
 I do not believe the mentioned conflict exists.  The aim of these
 calculator-like devices is to make sure that no malware, virus etc can
 create unauthorized transactions.  The user should still be able to
 debug, and inspect the software in the calculator-like device, or
 virtual software compartment, just that installation of software or
 upgrades into that area should be under direct explicit user control.
 (eg with BIOS jumper required to even make any software change!)

 The ring -1 and loss-of-control aspects of TPM are different, they are
 saying that you are not really root on your own machine anymore!  In
 the sense that if you do load under a debugger the remote party can
 tell this and refuse to talk with you.

I agree with Adam that the unique and defining aspect of TPM technology
is this property that users can prove their machine state without being
able to lie about it (modulo hardware attacks etc).  This can easily work
to the user's detriment - lying is often useful - but could sometimes
be to the user's advantage as well - being able to provably tell the
truth is useful too.

In the case of bank security, the question is whether there is any
point in trying to keep users from being able to falsify information
about their system configuration and software status.  Generally, the
user has no incentive to do so.  The question is whether attackers could
somehow exploit the ability of users to make undetected changes to their
secure computing base via social engineering and similar hacks.

In the case of the calculator-like device, for example, if it is fully
reprogrammable by the user, is there a risk that he could be fooled
into hooking it up to his computer in that mode and letting attackers
change its workings?  Or in the case of a TPM-like chip with an owner
override, could he be manipulated into using the override so as to make
fake banking software look real?

Such questions have two sides to them: the case of a user who does
get fooled into taking these actions and is harmed by them; and the
case of a user who merely pretends to have gotten tricked like this
in order to escape liability for transactions he truly did originate.
Defending against the latter class of frauds may give the bank incentive
to prefer systems where users cannot override their security, so as to
reduce the chance of false repudiations.

Looking at the system as a whole, then, there may indeed be a case for
financial security systems that cannot be overridden by end users.
If such measures reduce the overall costs of fraud in the system,
then users do benefit at least indirectly from giving up this degree
of control.  Sometimes in life, paradoxically, you do better by being
able to give up certain options, in a verifiable way.  TPM technology's
benefits to the user would arise from such paradoxical situations.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: The bank fraud blame game

2007-07-02 Thread Hal Finney
[EMAIL PROTECTED] (Peter Gutmann) writes:
 (The usage model is that you do the UI portion on the PC, but perform the
 actual transaction on the external device, which has a two-line LCD display
 for source and destination of transaction, amount, and purpose of the
 transaction.  All communications enter and leave the device encrypted, with
 the PC acting only as a proxy.  Bill of materials shouldn't be more than about

In theory the TPM was supposed to allow this kind of thing.  The idea
was that the OS would support secure applets that could not be molested
by legacy software.  Only such an applet would have access to your
payment information.  Some specialized, perhaps customized screen would
be displayed by the applet to get you to authorize the final transfer.

This was one of the main goals of the TPM as I understood the concept.
Unfortunately everyone got focused on the DRM aspect and that largely
torpedoed the whole idea.  Still we might see it eventually.  Research
in this direction is still going on, particularly in IBM's Integrity
Measurement Architecture[1] and some of the new security extensions to
the Xen virtualization software[2].

Hal Finney

[2] , also

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Free Rootkit with Every New Intel Machine

2007-06-27 Thread Hal Finney
Peter Gutmann writes:
 BitLocker just uses the TPM as a glorified USB key (sealing a key in a TPM is
 functionally equivalent to encrypting it on a USB key).  Since BitLocker isn't
 tied to a TPM in any way (I'm sure Microsoft's managers could see which way
 the wind was blowing when they designed it), it's not going to be TPM's killer

Actually BitLocker can use the TPM's measured boot capability for
additional security.  This requires a TPM-aware BIOS, which hashes
the disk's Master Boot Record into the TPM Platform Configuration
Registers before executing it, as well as measuring other system software

The disk encryption key is sealed to the TPM PCR values and the chip
won't release it if the boot sequence is different.  This means that
if you want to attack by, for example, booting from a Linux Live CD or
an external USB drive, the chip won't relase the encryption key even if
you guess the PIN right.

(Some) details at the BitLocker Drive Encryption Technical Overview page:

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

RE: Free Rootkit with Every New Intel Machine

2007-06-26 Thread Hal Finney
Ian Farquhar writes:
 [Hal Finney wrote:]
  It seems odd for the TPM of all devices to be put on a pluggable module as 
  shown here.  The whole point of the chip is to be bound tightly to the 
  motherboard and to observe the boot and initial program load sequence.

 Maybe I am showing my eternal optimist side here, but to me, this
 is how TPM's should be used, as opposed to the way their backers
 originally wanted them used.  A removable module whose connection to
 a device I establish (and can de-establish, assuming the presence of
 a tamper-respondent barrier such as a sensor-enabled computer case to
 legitimize that activity) is a very useful thing to me, as it facilitates
 all sorts of useful applications.  The utility of the original intent
 has already been widely criticised, so I won't repeat that here.  :)

Would that basically be the same as a removable smart card or
crypto token?  Those do exist and I agree that they have many useful
applications.  However their purpose is somewhat different from the TPM,
which is more specialized.

 It also shows those interesting economics at work.  The added utility of
 the TPM module (from the PoV of the user) was marginal at best despite
 all claims, yet it facilitated functionality which was contrary to
 most user's interests.  The content industry tried to claim that the
 TPM module would facilitate the availability of compelling content -
 which they tried to sell as it's user utility - but like most of their
 claims it was a smoke and mirrors trick.

At this point we are reduced to speaking hypothetically.  The TPM has
not provided either much benefit or much harm so far.  It has not (AFAIK)
been used to protect any content, for good or evil.  It has instead only
been used as a sort of glorified, non-removable smart card, which indeed
does not provide much utility.

 Consequently, the razor-edged economics of the motherboard and desktop
 industry has comprehensively rejected TPM except in certain specialized
 marketplaces where higher profit margins are available (eg. Servers,
 corporate desktops).  The chipset manufacturers have also failed to add
 this functionality to their offerings to date.

 Now Vista has added Bitlocker, which arguably adds a user valuable feature
 for which a TPM module is needed (yes, you can run it without TPM, but
 it's painful).  I wonder if we'll start to see more TPM connectors
 appearing, or even full TPM modules on motherboards and cores on south
 bridge dies?

I think the focus is likely still to be on laptop systems where the
benefits of an encrypted file system are especially high.  However if
Bitlocker comes down to the lower level Vistas then we may see TPMs
start to appear on lower end laptops.

 Personally, I'd like to see a TPM implemented as a tamper-respondent
 (ie. Self-powered) module mounted on the motherboard in a socket which
 allows removal detection.  That way you get the flexibility of moving
 the module, with the safety of a programmed response to an unauthorized

Interesting idea, although it's not clear what you would do with it.
The TPM architecture is enormously complex but it is entirely focused
on binding a TPM to a platform.  Breaking that rule would invalidate so
much of the TPM design that you might do better starting with a new chip
with its own functions and purpose.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Free Rootkit with Every New Intel Machine

2007-06-25 Thread Hal Finney
 at the last minute.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Public key encrypt-then-sign or sign-then-encrypt?

2007-05-16 Thread Hal Finney
James A. Donald writes:
 The flaw in the protocol that you point out is that
 Carol can allow Alice to use her public key without
 having to reveal the public key to Alice, so that Alice
 can pretend to be Carol.  Thus the flaw is that with
 prearrangement, Carol may prove to one other person, but
 to no one else, that Bob is saying such and such to
 Carol, provided she knows in advance that Bob is going to say it.
 Is there any way to fix this without introducing an
 additional exponentiation?  Perhaps by introducing an
 additional multiplication? It does not seem worth while
 introducing an additional public key operation, for such
 a low value attack.

In theory there is no way to prevent this, because Carol can always do
whatever she needs to do to decrypt using her secrets, and then prove
in zero knowledge to Alice that she did it correctly.  As long as Alice
sees via physical surveillance that the packets come from Bob, Carol
can convince her of what is inside of them.

In practice a full ZK proof is often not needed, as in the example you
give of defeating sign-then-encrypt in a hybrid encryption scheme.
Note that it is easy to prove that an RSA or ElGamal/DH decryption
is valid even without revealing your long term secret keys.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: More info in my AES128-CBC question

2007-05-13 Thread Hal Finney
Earlier someone asked about comparisons between full-width CFB and CBC.
They are very similar in certain ways. For example, the sequence of
operations for both are the same: xor the next block of plaintext; encrypt
the result; xor the next block of plaintext; encrypt the result; and so
on. The difference relates to the handling of the IV and the last block;
and more importantly, to where in this chain we define the output to be.
For CBC the output is after the encrypt steps; for CFB the output is
after the xor teps.  This also implies that, except for the first and
last blocks, you can transform a CBC encryption into a CFB encryption
by xoring the plaintext into the ciphertext, and vice versa.

In terms of IV, CFB encrypts the IV and then xors with the first block
of plaintext.  CBC xors the IV with the plaintext and then encrypts.
So you have a little more flexibility in terms of choosing your IV,
with CFB mode.  A simple counter should be good enough.  However the
penalty for erroneously reusing an IV is worse; it reveals the XOR of the
respective plaintexts, whereas in CBC mode it will only reveal whether
the plaintexts are identical.

Hal Finney
PGP Corporation

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Was a mistake made in the design of AACS?

2007-05-05 Thread Hal Finney
Allen [EMAIL PROTECTED] writes:
 I know I'm in over my head on this so my apologies, but if the 
 key is used in one machine in a product line - Sony DVD players 
 say - then if they find the one machine that it came from and 
 disable it, wouldn't figuring out the key for the next machine in 
 the production run be relatively trivial as the algorithm and 
 hardware implementation used by all machines of a give run be the 
 same? Therefore, couldn't one buy several of them and use them 
 one after another as they are discovered and disabled?

Perhaps so, depending on the nature of the crack.  It may require
unsoldering chips from the machine motherboard or other rather difficult
to perform operations that would not be possible for average users.
Keep in mind that each machine costs several hundred dollars, and they
will be turned into bricks once revoked.  This raises the question of
who is bankrolling this effort and what his motivations are.

 So, in order to prevent any of those machines from being used 
 they'd have to disable a whole lot of machines owned by ordinary 
 individuals, right? What are the downside risks for Sony in doing 

I imagine it is safe to say that this is not a step that AACSLA would take
lightly.  If they ever did this then I suppose the machine manufacturer
would have to provide owners of the affected models with upgrades to
newer machines.

It's very hard to predict the future and it is not clear to me that
we will get into a scenario where a very small number of sacrificial
machines are the source of every HD movie being uploaded to the pirate
nets, such that when these few machines are revoked, immediately
another few machines are swapped in to replace them.  It would require
a relatively large degree of coordination among what I would imagine
is a generally loose affiliation of attackers with diverse motivations.
But as I said, my crystal ball is foggy.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Yet a deeper crack in the AACS

2007-05-05 Thread Hal Finney
 Article AACS cracks cannot be revoked, says hacker

 Excerpt: The latest attack vector bypasses the encryption performed
 by the Device Keys -- the same keys that were revoked by the WinDVD
 update -- and the so-called 'Host Private Key,' which as yet has not
 been found. This was accomplished by de-soldering the HD DVD drive's
 firmware chip, reading its contents, and then patching it. Once that
 was done, the firmware was soldered back onto the drive.

This article was not too accurate, and further progress has been
made.  At this point it is possible to remotely patch the firmware
of a particular kind of HD-DVD drive so that it will provide certain
information without the usually required authentication.  This makes it
easy to retrieve the per-disk Volume ID, which must be combined with
the widely-published Processing Key to generate the media keys that
can decrypt content.  If this Processing Key is invalidated on future
releases, this hack will not be useful until new keys are discovered.
It provides only part of the picture.

The hack was a real accomplishment because firmware updates had to
be authenticated with what was apparently something like an AES-based
CBC-MAC.  The hackers had to figure this out without much background
in cryptography and working only with dumps of the firmware that used a
somewhat obscure embedded CPU.  They had to figure out what CPU was being
used, find a disassembler for it, and examine assembly language dumps to
deduce that crypto was involved, recognize AES, and see how to create
their own checksums that would make their firmware updates succeed.
Just goes to show the motivation and hard work that hackers bring to
these efforts, largely for the love of the challenge.

It's possible that the ability to modify firmware will lead to more
successes for the hackers in the future, perhaps helping them to break
into future versions of software players to extract their embedded keys.
I peruse the forums from time to time, where this work took
place right out in the open, before the public eye.  Definitely some
smart people involved there.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

AACS and Processing Key

2007-05-02 Thread Hal Finney
 much information about which device was cracked in order
to extract the key.  This might leave AACSLA in a quandary about what to
revoke in order to fix the problem.  However in this particular case the
attackers made little attempt to conceal their efforts and it was clear
which software player(s) were being used.  This may not be the case in
the future.

AACSLA has announced that they will be changing the processing keys used
in disks which will begin to be released shortly.  Software players have
been updated with new device keys, indicating that the old ones will be
revoked.  In the context of the subset-difference algorithm, there will
now probably be a few encryptions necessary to cover the whole tree while
revoking the old software player nodes as well as the pre-revoked node.
This will make the processing key which has been published useless for
decrypting new disks.

Because processing keys do not unambiguously point to their source,
AACSLA may choose to set up subset-difference encryptions in which
each software player is part of a different subtree and therefore uses
a different processing key.  This might require a few more encryptions
than the minimal number that subset-difference allows, but it would
reduce the chance that AACSLA would find themselves unable to determine
the source of a published processing key.  This will only work as long
as attackers restrict themselves to the relatively few software players.
If some group were to succeed in extracting keys from a hardware player
and publish a processing key that might apply to the majority of hardware
players in use, AACSLA would seemingly have no way to determine how to
address the problem.

Now I must confess that this already long message has oversimplified the
AACS system in certain respects.  First, the subset-difference system is
only carried on for the lowest 22 levels of the 31 level tree.  There are
effectively 512 independent trees where the algorithm is applied, each
with a single pre-revoked leaf node.  However at this time it appears
that only one is in use.

Second, the processing key is not actually the same as the node's device
key, but rather is a hash of the device key.  Further, the exact details
of how you go from the processing key to the various disk content keys
involve several levels of indirection and encryption.

Third, even given the processing key, some of the information needed
to derive all of the disk's content is not easily available.  One piece
needed is a per-title Volume ID which is not readable from the disk in a
straightforward way.  Volume IDs have been discovered by eavesdropping
on the USB bus connected to a disk player, or by hacking disk player
firmware.  At this point it is hard for typical end users to read
Volume IDs, so knowing the processing key is not generally sufficient
to read disks.  Databases of Volume IDs have been published online,
but disk media keys could just as easily have been published.

Speculating now, the AACS system is flexible but it is possible that
publication of processing keys may not have been fully anticipated by the
designers.  The difficulty of tracing processing keys to their source in
an environment in which new disks may require many weeks or even months of
lead time may interfere with the planned revocation system.  The current
processing key will soon be rendered invalid for new releases, so AACSLA's
aggressive legal tactics seem disproportionate compared to the relative
unimportance of this particular key.  Perhaps these legal actions are
primarily intended to limit distribution of future processing keys that
are found on the next set of disk releases.  That would further point
to technical difficulties in revocation strategy when a new processing
key is published.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Was a mistake made in the design of AACS?

2007-05-02 Thread Hal Finney
Perry Metzger writes:
 I will again solicit suggestions about optimal strategies both for
 the attacker and defender for the AACS system -- I think we can learn
 a lot by thinking about it. It would be especially interesting if
 there were modifications of the AACS system that would be more hardy
 against economic attacks -- can you design the system so that slow
 key revelation is not an economic disaster while still maintaining an
 offline delivery model with offline players entirely in the enemy's
 control? I don't think you can, but it would be very interesting to
 consider the problem in detail.

Ed Felten has blogged a number of ideas along these lines:

By this point in our series on AACS (the encryption scheme used in
HD-DVD and Blu-ray) it should be clear that AACS creates a nontrivial
strategic game between the AACS central authority (representing the
movie studios) and the attackers who want to defeat AACS. Today I want
to sketch a model of this game and talk about who is likely to win...

Felten focuses on the loss of revenue due to extraction of device keys
and subsequent file sharing of decrypted content.  AACS has a mechanism
called sequence keys to watermark content and allow it to be traced
back to the player that created it.  Felten assumes that attackers would
publish decrypted movies, AACSLA would then trace them back to the broken
device, and revoke that device in future releases.

The optimal strategy depends on his parameters C, the cost in time it
takes for attackers to break into new devices and extract keys; and L,
the commercial lifetime of a new disk.  Felten writes:

It turns out that the attacker's best strategy is to withhold any newly
discovered compromise until a 'release window' of size R has passed
since the last time the authority blacklisted a player. (R depends in
a complicated way on L and C.) Once the release window has passed,
the attacker will use the compromise aggressively and the authority
will then blacklist the compromised player, which essentially starts
the game over. The studio collects revenue during the release window,
and sometimes beyond the release window when the attacker gets unlucky
and takes a long time to find another compromise.

He estimates that C is measured in weeks and L in months, which bodes
ill for the studios, as his model predicts that studios will receive
the fraction C/(C+L) of their potential revenues if no piracy occured,
and CL makes this fraction small.

I see a couple of problems with his model.  First, it may be that by
publishing processing keys instead of device keys or movie content, it
will be harder to make the traitor tracing algorithm work and AACSLA may
be thwarted in their attempt to revoke the broken device.  I'm not sure
I understand the system well enough to know whether there are effective
countermeasures for AACSLA against this attacker strategy.  Threats of
legal action do not appear to be achieving much success.

Second, there is a long lead time between when AACSLA determines to
update the processing keys and other components of the subset difference
scheme, and when the disks actually reach the public.  This is bad for
the studios and probably effectively increases L.

On the other hand I suspect his L estimate of months is excessive;
8 of the Amazon's 10 top selling DVDs were released since April 24.
As with other media like CDs, it is likely that the bulk of revenues
arrive during the first few weeks of release.  If they can protect that
window then they might view the system as achieving at least some of
its goals.  But these other considerations will work against them.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: can a random number be subject to a takedown?

2007-05-01 Thread Hal Finney
 My question to the assembled: are cryptographic keys really subject to
 DMCA subject to takedown requests? I suspect they are not
 copyrightable under the criterion from the phone directory

A sample demand letter from the AACS Licensing Authority appears at:

From what I can see, there is no claim that the key is copyrighted.
Rather, the letter refers to the provisions of the DMCA which govern
circumvention of technological protection measures.  It demands that
the key be taken down in order to avoid legal liability.

This seems odd to me because my understanding of the DMCA's
anti-circumvention provisions is that they are criminal rather than civil
law.  Violations would lead to charges from legal authority and not from a
copyright owner.  So it's not clear that AACSLA has any power to enforce
these demands, other than trying to get some government agency involved.

The letter specifically cites 17 USC 1201(a)2 and (b)1, which can be read

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Governance of anonymous financial services

2007-03-30 Thread Hal Finney
Steve Schear writes:
 Here is the situation.  An on-line financial service, for example a DBC 
 (Digital Bearer Certificate), operator wishes his meat space identity, 
 physical whereabouts, the transaction servers and at least some of the 
 location(s) of the service's asset backing to remain secret...

Pretty tough to do much with crypto in this situation.  My
software was an attempt to create what Nick Szabo called bit gold,
transferrable certificates that had intrinsic rarity.  It uses trusted
computing concepts to create RSA signatures that are backed by hash
collisions.  Unfortunately rarity does not automatically translate into
value, so even though the system was highly inflation-resistant it was
not too successful in attracting users.

 The service 
 provides frequent, maybe even real-time, data on its asset backing versus 
 currency in circulation. The operator wishes to provide some assurance to 
 his clients that the backing and the amount of currency in circulation are 
 in close agreement.  The mint's backing need not be in a single location 
 nor in the sole possession of the operator.

Maybe he could publish a picture of the backing commodities, and design
the system so that everyone could see how much money was in circulation?

Keep in mind that this is only part of the trust picture.  Showing that
the backing is there won't prevent this anonymous operator from absconding
with the funds in the future.  That would be one of my concerns if I
were a user.

 If the backing is distributed among a multitude of holders (e.g., in a 
 fashion similar to how Lloyds backs their insurance empire), who's 
 identities are kept secret until audit time and then only a few, randomly 
 selected, names and claimed deposit amounts are revealed to the auditors, 
 might this statistical sampling and the totals projected from the results 
 be a reasonable replacement for 'full asset' audit?  To protect the 
 identities of the holders could a complete list of the hashes of each name 
 and claimed deposit be revealed to the auditors, who then select M of N 
 hashes whereupon the operator reveals only those identities and claimed 
 deposits work cryptographically?

One problem is the holders could collude and play a shell game.
Suppose that 30% of the holders were going to be asked to reveal their
assets, then the company could back only 30% of the currency, and
redistribute the assets to the selected holders before the auditors come.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: virtualization as a threat to RNG

2007-03-23 Thread Hal Finney
Dan Geer wrote:
 Quoting from a discussion of threat posed by software virtualization as 
 found in Symantec's ISTR:xi, released today:

  The second type of threat that Symantec believes could emerge is 
  related to the impact that softwarevirtualized computers may have on 
  random number generators that are used inside guest operating systems 
  on virtual machines

There was related discussion a couple of months ago on the IRTF Crypto
Forum Research Group mailing list.  The question is what security problems
might arise with increased use of virtualization, in particular state
rollbacks causing reuse of nonces and other values that are required to
be unique.

Wei Dai summarized suggestions from the thread at:

: There have been several specific and practical suggestions, but they were
: spread over several messages in the discussion. I'll summarize here:
: 1. Use random IVs instead of counter or state-derived IVs.
: 2. For any crypto scheme that uses random numbers or IVs, generate the
: random numbers/IVs after the message to be encrypted and/or authenticated is
: fixed.
: 3. Use the operating system's secure RNG to generate these random
: numbers/IVs and hash in the current time and/or the message to make sure
: random numbers are not reused on different messages.
: 4. As an alternative to 1-3 above, switch to a crypto scheme such as SIV
: that is specifically designed to tolerate nonce reuse.

The thread index will allow reading more of the discussion at
under the title, how to guard against VM rollbacks.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: IBM donates new privacy tool to open-source Higgins

2007-02-04 Thread Hal Finney
John Gilmore forwards:

 IBM donates new privacy tool to open-source
   By  Joris Evers
   Staff Writer, CNET
   Published: January 25, 2007, 9:00 PM PST

 IBM has developed software designed to let people keep personal  
 information secret when doing business online and donated it to the  
 Higgins open-source project.

   The software, called Identity Mixer, was developed by IBM  
 researchers. The idea is that people provide encrypted digital  
 credentials issued by trusted parties like a bank or government agency  
 when transacting online, instead of sharing credit card or other  
 details in plain text, Anthony Nadalin, IBM's chief security architect,  
 said in an interview.

I just wanted to note that the idemix software implements what we
sometimes call Camenisch credentials.  This is a very advanced credential
system based on zero knowledge and group signatures.  The basic idea is
that you get a credential on one pseudonym and can show it on another
pseudonym, unlinkably.  More advanced formulations also allow for
credential revocation.  I don't know the specifics of what this software
implements, and I'm also unclear about the patent status of some of the
more sophisticated aspects, but I'm looking forward to being able to
experiment with this technology.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: analysis and implementation of LRW

2007-01-25 Thread Hal Finney
To clarify a couple of points with regard to IEEE P1619 and LRW.

The original proposal which P1619 called LRW was actually a particular
concrete instantiation of a general construction from the LRW paper
(Liskov, Rivest and Wagner, Tweakable Block Ciphers, Crypto 02, ).

The LRW construction was C = E_k(P xor h(T)) xor h(T) where E_k
is a block cipher with key k, T is the tweak and h(T) is a keyed
almost-xor-universal function.  P1619 instantiated E as AES and h as
galois field multiplication by a secret constant value: h(T) = k2*T
where T is the block number.  This is what they called LRW and it
has the weakness described, that if you have two consecutive blocks
containing k2 and zero, P xor h(T) can be the same for both of them.
This is what the group called a collision, meaning two blocks whose
input to the AES is the same.  For this simple definition of h(T) as
k2*T a collision can reveal k2.

However this is not a general flaw in LRW, it is merely a problem with
this very simple instantiation of the construction.

In fact the replacement, which the group calls XTS, is also an instance
of LRW.  Based on work by Rogaway, the construction is the same as above
but the universal hash h(T) = E_k2(T1) * alpha^T2, where T1 are the
leftmost bits of the block number T and T2 are the rightmost bits (alpha
is a primitive root, and the math is finite field).  Rogaway proved that
this hash is universal and hence this is an instance of LRW and is secure.

So it is an over-simplification to say that P1619 found LRW insecure
and replaced it.  P1619 found that a particularly simple instantiation
of LRW had this problem when encrypting part of its key, and substituted
a more complicated version of LRW which appears to be largely immune to
the problem.  P1619 is still using LRW and it should still be considered
a very seminal and useful cryptographic construction.

It should be noted that almost no cryptographic proofs of security work
when arbitrary functions of the key are allowed as inputs to other parts
of the cipher, and at this point we must largely rely on heuristic and
informal arguments to see whether any weaknesses are real or merely

Hal Finney
PGP Corporation
P1619 Member

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

RE: Exponent 3 damage spreads...

2006-09-21 Thread Hal Finney
Anton Stiglic writes:
 I tried coming up with my own forged signature that could be validated with
 OpenSSL (which I intended to use to test other libraries). ...

 Now let's look at s^3

 This has the form we are looking for, the 01 FF FF ... FF header that ends
 with 00, and then we have 
 which is the d we started out with, and the rest is the GARBAGE part.

 Only one problem, s^3 is larger than m, so if we computed modexp(s, 3, m)
 the result would be rounded out modulo m and we would loose the above

This is not correct.  I counted, and the number shown above has 762
hex digits.  It is 3057 bits long, compared to m which is 3072 bits.
It is not bigger than m, and does not need to be adjusted.  3057 is
precisely the correct number of bits for a PKCS-1 padded value for a
3072 bit exponent.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Why the exponent 3 error happened:

2006-09-17 Thread Hal Finney
For another example of just how badly this kind of thing can be done,
look at this code excerpt from Firefox version, which is the
fixed version.  There are two PKCS-1 parsing functions, one which returns
the hash and its prefix, the other of which is given the hash and asked
whether it matches the RSA-signed value.  This is from the latter one:

 * check the padding that was used
if (buffer[0] != 0 || buffer[1] != 1)
goto loser;
for (i = 2; i  modulus_len - hash_len - 1; i++) {
if (buffer[i] == 0)
if (buffer[i] != 0xff)
goto loser;

 * make sure we get the same results
if (PORT_Memcmp(buffer + modulus_len - hash_len, hash, hash_len) != 0)
goto loser;

return SECSuccess;

Here, buffer holds the result of the RSA exponentiation, of size
modulus_len, and we are passed hash of size hash_len to compare.

I don't think this code is used, fortunately.  It will accept anything
of the form 0, 1, 0, garbage, hash.  Just goes to show how easy it is
to get this kind of parsing wrong.

(Note, this is from 

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Real World Exploit for Bleichenbachers Attack on SSL from Crypto'06 working

2006-09-15 Thread Hal Finney
Erik Tews writes:
 At least 3 major webbrowsers on the marked are shipped by default with
 CA certificates, which have signed other intermediate CAs which use
 rsa1024 with exponent 3, in their current version. With this exploit,
 you can now sign arbitary server certificates for any website of your
 choice, which are accepted by all 3 webbrowsers without any kind of

Is that true, did you try all 3 web browsers to see that they don't give
a warning message?  It's not enough that they accept a CA with exponent
3, they also have to have the flaw in verification that lets the bogus
signature through.

If it is true, if three different widely used webbrowsers are all
vulnerable to this attack, it suggests a possible problem due to the
establishment of a cryptographic monoculture.  If it turns out that
the same cryptographic library is used in all three of these browsers,
and that library has the flaw, then this reliance on a single source
for cryptographic technology could be a mistake.

Now in practice I don't think that Internet Explorer and Mozilla/Firefox
use the same crypto libraries, so either these are not two of the three,
or else they have independently made the same error.  It would be nice
to know which it is.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Why the exponent 3 error happened:

2006-09-15 Thread Hal Finney
James Donald writes:
 There is no need, ever, for the RSA signature to encrypt
 anything other than a hash, nor will their ever be such
 a need.  In this case the use of ASN.1 serves absolutely
 no purpose whatsoever, other than to create complexity,
 bugs, and opportunities for attack.  It is sheer
 pointless stupidity, complexity for the sake of
 complexity, an indication that the standards process is

Actually there is something besides the hash there: an identifier for
which hash algorithm is used.  The ASN.1 OID was, I suppose, a handy and
already-existant mechanism for universal algorithm identification numbers.

Putting the hash identifier into the RSA signed data prevents hash
substitution attacks.  Otherwise the hash identifier has to be passed
unsigned, and an attacker could substitute a weak hash algorithm and find
a second preimage that matches your signed hash.  Maybe that is not part
of a threat model you are interested in but at least some signers don't
want their hash algorithms to be changed.

BTW I want to mention a correction to Peter Gutmann's post: as I
understand it, GnuPG was not vulnerable to this attack.  Neither was PGP.
The OpenPGP standard passes the hash number outside the RSA signed data
in addition to using PKCS-1 padding.  This simplifies the parsing as it
allows hard-coding the ASN-1 prefix as an opaque bit string, then doing
a simple comparison between the prefix+hash and what it should be.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Exponent 3 damage spreads...

2006-09-14 Thread Hal Finney
Peter Gutmann writes:
 But wait, there's more!  From what I understand of the attack, all you need
 for it to work is for the sig.value to be a perfect cube.  To do this, all you
 need to do is vary a few of the bytes of the hash value, which you can do via
 a simple brute-force search.  So even with a perfect implementation that does
 a memcmp() of a fixed binary string for all the data present but the hash, the
 attack still works.

I don't think this works. I tried with a 1024 bit key.  We want a cube root of
something between:




But actually the nearest cube root is:


Cubing this gives:


and cubing the next higher value gives:


So no variation on the hash value will produce something that is a
perfect cube.  Now, this is specific to 1024 bit keys, but larger keys
should be even more unfavorable.  As a general rule we can only force
the top 1/3 of the bits to be 1s as required, and the chances of getting
lucky will be worse for larger keys.

We could start adding in multiples of the modulus and look for perfect
cubes again, but basically the odds against are 1 in N^(2/3) so there
is no point.

Hal Finney
PGP Corporation

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Raw RSA

2006-09-08 Thread Hal Finney
Alexander Klimov asks:
 If an attacker is given access to a raw RSA decryption oracle (the
 oracle calculates c^d mod n for any c) is it possible to extract the
 key (d)?

This is equivalent to asking whether factoring reduces to RSA inversion.
That is, given access to an RSA inversion oracle, can you factor the
modulus?  (Factoring the modulus is equivalent to finding d.)

Then see Breaking RSA May Not Be Equivalent to Factoring by Boneh and
Venkatesan, Eurocrypt 98.  Abstract (with my added emphasis):

We provide evidence that breaking low-exponent RSA cannot be equivalent
to factoring integers. We show that an algebraic reduction from factoring
to breaking low-exponent RSA can be converted into an efficient factoring
FACTORING INTEGERS. Our result suggests an explanation for the lack of
progress in proving that breaking RSA is equivalent to factoring. We
emphasize that our results do not expose any specific weakness in the
RSA System.

So the answer would appear to be no, an oracle for RSA does not help in
factoring and therefore will not reveal d.

See also
The One-More-RSA-Inversion Problems and the Security of Chaum's Blind
Signature Scheme by Bellare et al for some discussion of this issue.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Bleichenbacher's RSA signature forgery based on implementation error

2006-08-30 Thread Hal Finney
At the evening rump session at Crypto last week, Daniel Bleichenbacher
gave a talk showing how it is possible under some circumstances to
easily forge an RSA signature, so easily that it could almost be done
with just pencil and paper.  This depends on an implementation error,
a failure to check a certain condition while verifying the RSA signature.
Daniel found at least one implementation (I think it was some Java crypto
code) which had this flaw.  I wanted to report on his result here so that
other implementers can make sure they are not vulnerable.  Be aware that
my notes were hurried as Daniel had only a few minutes to talk.

The attack is only good against keys with exponent of 3.  There are
not too many of these around any more but you still run into them
occasionally.  It depends on an error in verifying the PKCS-1 padding
of the signed hash.

An RSA signature is created in several steps.  First the data to be
signed is hashed.  Then the hash gets a special string of bytes in ASN.1
format prepended, which indicates what hash algorithm is used.  This data
is then PKCS-1 padded to be the width of the RSA modulus.  The PKCS-1
padding consists of a byte of 0, then 1, then a string of 0xFF bytes,
then a byte of zero, then the payload which is the ASN.1+hash data.

00 01 FF FF FF ... FF 00  ASN.1  HASH

The signature verifier first applies the RSA public exponent to reveal
this PKCS-1 padded data, checks and removes the PKCS-1 padding, then
compares the hash with its own hash value computed over the signed data.

The error that Bleichenbacher exploits is if the implementation does
not check that the hash+ASN.1 data is right-justified within the PKCS-1
padding.  Some implementations apparently remove the PKCS-1 padding by
looking for the high bytes of 0 and 1, then the 0xFF bytes, then
the zero byte; and then they start parsing the ASN.1 data and hash.
The ASN.1 data encodes the length of the hash within it, so this tells
them how big the hash value is.  These broken implementations go ahead
and use the hash, without verifying that there is no more data after it.
Failing to add this extra check makes implementations vulnerable to a
signature forgery, as follows.

Daniel forges the RSA signature for an exponent of 3 by constructing a
value which is a perfect cube.  Then he can use its cube root as the
RSA signature.  He starts by putting the ASN.1+hash in the middle of
the data field instead of at the right side as it should be.  Graphically:

00 01 FF FF ... FF 00  ASN.1  HASH  GARBAGE

This gives him complete freedom to put anything he wants to the right
of the hash.  This gives him enough flexibility that he can arrange for
the value to be a perfect cube.

In more detail, let D represent the numeric value of the 00 byte, the
ASN.1 data, and the hash, considered as a byte string.  In the case
of SHA-1 this will be 36 bytes or 288 bits long.  Define N as 2^288-D.
We will assume that N is a multiple of 3, which can easily be arranged
by slightly tweaking the message if neccessary.

Bleichenbacher uses an example of a 3072 bit key, and he will position
the hash 2072 bits over from the right.  This improperly padded version
can be expressed numerically as 2^3057 - 2^2360 + D * 2^2072 + garbage.
This is equivalent to 2^3057 - N*2^2072 + garbage.  Then, it turns out
that a cube root of this is simply 2^1019 - (N * 2^34 / 3), and that is
a value which broken implementations accept as an RSA signature.

You can cube this mentally, remembering that the cube of (A-B) is A^3 -
3(A^2)B + 3A(B^2) - B^3.  Applying that rule gives 2^3057 - N*2^2072
+ (N^2 * 2^1087 / 3) - (N^3 * 2^102 / 27), and this fits the pattern
above of 2^3057 - N*2^2072 + garbage.  This is what Daniel means when
he says that this attack is simple enough that it could be carried out
by pencil and paper (except for the hash calculation itself).

Implementors should review their RSA signature verification carefully to
make sure that they are not being sloppy here.  Remember the maxim that in
cryptography, verification checks should err on the side of thoroughness.
This is no place for laxity or permissiveness.

Daniel also recommends that people stop using RSA keys with exponents
of 3.  Even if your own implementation is not vulnerable to this attack,
there's no telling what the other guy's code may do.  And he is the one
relying on your signature.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: switching from SHA-1 to Tiger ?

2006-07-11 Thread Hal Finney
Zooko writes:
 By the way, the traditional practice of using a hash function as a 
 component of a MAC should, in my humble opinion, be retired in favor of 
 the Carter-Wegman alternative such as Poly-1305 AES [7].

This is a great topic where there are lots of pros and cons.  The CW
MACs like UMAC and Poly1305-AES have advantages including speed and
provable security.  However the recent result Perry cited by Bellare,, argues that HMAC relies only on the
compression function being a PRF, and the CW MACs also need a PRF.
So perhaps their security properties will not turn out to be so different.

From the security implementor's POV, the speed of the CW MACs must
be balanced against potentially greater difficulty in using them.
They are not black-box drop-in replacements for HMAC.  CW MACs rely on
the presence of a unique nonce per message (and per key).  This can be
as simple as a sequence number, or perhaps a random string.  But either
one may require adding state and/or environmental access to what is a
simple stateless function with HMAC.

CW MACs also have the property that they may allow single brute-force
forgeries to be easily extended to multiple forgeries.  The ease or
difficulty of this extension will depend on details of the MAC design,
but in principle, the CW security properties allow for it.  This means
that MACs of moderate length, like 64 bits or less, need to be evaluated
much more critically with a CW MAC implementation.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: NIST hash function design competition

2006-07-11 Thread Hal Finney
James Donald writes:
 My understanding is that no actual vulnerabilities have
 been found in Rijndael.  What has been found are reasons
 to suspect that vulnerabilities will be found.

Yes, I think that's correct on the theoretical side.  I was also thinking
of some of the implementation issues which have shown up, particularly
timing and cache attacks.  AES is proving to be difficult to immunize
against these problems.  A good discussion by Bernstein is presented
in, where he asks,
regarding this AES issue, How did this happen?:

: Was the National Institute of Standards and Technology unaware of
: timing attacks during the development of AES? No. In its âReport on the
: development of the Advanced Encryption Standard, NIST spent several pages
: discussing side-channel attacks, specifically timing attacks and power
: attacks. It explicitly considered the difficulty of defending various
: operations against these attacks.  For example, NIST stated in [19,
: Section 5.1.5] that MARS was âdifficult to defend against these attacks.
: Did NIST decide, after evaluating timing attacks, that those attacks
: were unimportant? No. Exactly the opposite occurred, as discussed below.
: So what went wrong? Answer: NIST failed to recognize that table lookups
: do not take constant time. âTable lookup: not vulnerable to timing
: attacks, NIST stated in [19, Section 3.6.2]. NIST's statement was,
: and is, incorrect.
: NIST went on to consider the slowness of AES implementations designed
: to protect against side-channel attacks. For example, NIST stated
: that providing âsome defense for MARS meant âsevere performance
: degradation. NIST stated in [19, Section 5.3.5] that Rijndael gained a
: major speed advantage over its competitors when such protections are
: considered. This statement was based directly on the incorrect notion
: that table lookups take constant time. NIST made the same comment in
: its summary assessments of the finalists, and again in its concluding
: paragraph explaining the selection of Rijndael as AES.  See [19, Section
: 6.5] and [19, Section 7].

This is an example of a case where there doesn't seem to have been
enough time during the AES process for people to notice this oversight.
It probably didn't help that analysts had to spread their effort over
five main candidates.

Maybe it would be a good idea for NIST to add an extra phase where they
announce their proposed finalist, and ask everyone to focus all their
attention on potential weaknesses in this one function.  Since this is
exactly what will happen anyway immediately after the selection is made,
it might make sense to build a buffer period into the process to let
people take their final shots.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

NIST hash function design competition

2006-07-10 Thread Hal Finney
I was registering today for the Crypto conference and discovered that
immediately afterwards, and at the same site in Santa Barbara, CA, NIST
is holding a two-day workshop on hash function design.  The information
is here:

In response to the SHA-1 vulnerability that was announced in Feb. 2005,
NIST held a Cryptographic Hash Workshop on Oct. 31-Nov. 1, 2005 to solicit
public input on its cryptographic hash function policy and standards. NIST
continues to recommend a transition from SHA-1 to the larger approved
hash functions (SHA-224, SHA-256, SHA-384, and SHA-512). In response
to the workshop, NIST has also decided that it would be prudent in
the long-term to develop an additional hash function through a public
competition, similar to the development process for the block cipher in
the Advanced Encryption Standard (AES).

I had not heard that there had been an official decision to hold a new
competition for hash functions similar to AES.  That is very exciting!
The AES process was one of the most interesting events to have occured
in the last few years in our field.

Seemed like one of the lessons of that effort was that, even though it was
successful in terms of attracting the interest and hard work of some of
the top researchers in the field, in the end we have learned considerably
more about Rijndael's vulnerabilities only after the process was over.
Perhaps the intrinsic difficulty of cryptography makes this kind of outcome
inevitable.  But hopefully the hashing competition will learn from the AES
experience and make sure that it takes as much time as it needs to take.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Use of TPM chip for RNG?

2006-06-29 Thread Hal Finney
A few weeks ago I asked for information on using the increasingly
prevalent built-in TPM chips in computers (especially laptops) as a
random number source.  I got some good advice and want to summarize the
information for the benefit of others.

The TPM chip as spec'd by the Trusted Computing Group
( is a complex and controversial device.
Despite (or perhaps because of) all the fuss over it when the technology
was introduced, nothing much has happened with it and they are mostly
used to add a bit of security to encrypted files and such.  TPMs do have
hardware RNGs and I wanted to find out how to access this capability.

On Windows, there are several APIs available which can work.
The native API for the TPM is the Trusted Software Stack (TSS). This provides a
wide range of TPM-specific functions, including ones to access the RNG.
Another alternative is Microsoft's Crypto API (MS-CAPI).  CAPI uses a
plug-in architecture where Crypto Service Providers (CSPs) provide the
required functionality.  TPM-based CSPs allow access to TPM functions
via CAPI.  Third, the PKCS-11 (Cryptoki) API is designed for access
to smart cards, but TPM manufacturers often deliver PKCS-11 compatible
libraries for access to the chips.  Both CAPI and PKCS-11 have random
number functionality which can be used to access the TPM RNG.

The main problem in practice with using this functionality on Windows is
that there is as yet no standard for naming or locating the DLL's which
supply the necessary functions.  I am testing on an IBM Thinkpad with
an Atmel TPM, and it comes with DLL's that provide TSS, CAPI and PKCS-11
interfaces.  But all are supplied with non-standard names and located in
non-standard places.  Software to use these functions has to know where
the DLLs are and what they are called in order to load them explicitly.

The exception is MS-CAPI.  CAPI provides an interface to enumerate all
the CSPs, so if you can figure out which one is the TPM CSP you can then
use that one to generate random numbers.  One of the CAPI functions lets
you query to see if the CSP has hardware RNG support.  On my system,
this returns TRUE for the TPM CSP.  However, a colleague has a Dell
system with a different TPM and different software, and that TPM's CSP
does not set this bit.  So I don't have a foolproof method of figuring
out which CSP to use in order to access the TPM.  It might be possible
to hard-code the names of all known TPM CSPs but that would not be very
flexible going forward.

At this point MS-CAPI still looks like the best choice for
machine-independent access to the TPM RNG on Windows.  The ability to
reliably enumerate all the CSPs is much easier than hunting through the
disk to try to find a DLL to implement the TSS or PKCS-11 APIs.  OTOH if
you are building the software for a particular system and can build in
the location of the necessary DLL, one of the other APIs could work too.

On Linux systems, as I mentioned earlier, the standard appears
to be an open-source TSS implementation called Trousers, at .  This requires the Linux kernel to
have a TPM device driver built-in or as a loadable module.  This has
been available in the kernel since 2.6.12, but many distributions do
not enable it, even as a module, so some work is needed to make a kernel
with TPM support.  Then the Trousers software builds a daemon process,
tcsd, which opens /dev/tpm exclusively, and a library, libtspi, for
remote access to tcsd and the TPM.

If you want a cross-platform solution, TSS is probably the best approach
going forward.  As noted, at present the software support is a little
immature and some local configuration will be necessary - locating the
TSS DLL on Windows, and installing the TPM kernel support and Trousers
software on Linux.  Once this is done, the TSS API should provide for
cross-platform capability.  And of course it has additional functionality
if you want to use the TPM for more than just random number generation.

Intel Macs have TPM chips as well but I don't know of any software yet
that can access them.  Eventually I would expect a TSS solution to be
available on that platform as well.

Thanks again to the people who provided me information about these
various solutions!

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Use of TPM chip for RNG?

2006-06-12 Thread Hal Finney
Finding a good source of random bits is a frequent problem in
cryptographic applications.  Recently many computers have begun shipping
with a TPM chip, which among other things includes a hardware RNG.
Does anyone know of Windows software which can use the TPM for this
purpose?  Perhaps via MS CAPI, or some other API?

On Linux, the Trousers library,,
provides access to TPM functions including RNG.  Basically I'm looking
for something similar for Windows.

Given all the questions about trusted computing technology, it would be
nice to get some straightforward operational benefit from all those TPM
chips being installed.  I'll be happy to summarize results back to the
list if people want to contact me privately.

Thanks -

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: picking a hash function to be encrypted

2006-05-15 Thread Hal Finney
Travis H. writes:
 Excellent point.  When I wrote that I had strongly universal hashes in
 mind, like UMAC, where the hash is chosen from a family of functions
 based on some secret data shared by sender and recipient.  I
 mistakenly conflated them with ordinary hashes (which they are, once
 you pick one).  Thanks for catching that.

A point of terminology, strong universal hash functions are different
than what you are probably thinking of.

UMAC is a MAC, not a SU hash function.  It uses an almost-SU hash function
in its construction, but that's different.

Universal hashes and their variants (see
for a bibliography) are actually *weaker* than conventional hashes.
They can, in fact, be completely linear.  While you are right that the
hash is typically part of a parameterized family, once you pick one you
do not get an ordinary hash.  You are more likely to get an ordinary
polynomial that will not serve at all well as a crypto hash.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: what's wrong with HMAC?

2006-05-02 Thread Hal Finney
Travis H. writes:
 Ross Anderson once said cryptically,
  HMAC has a long story attched to it - the triumph of the
  theory community over common sense

 He wouldn't expand on that any more... does anyone have an idea of
 what he is referring to?

I might speculate, based on what you write here, that he believed that
the simpler, ad hoc constructions often used in the days preceding
HMAC were good enough in practice, and that the theoretical proofs of
security for HMAC were given too much weight.  The original HMAC paper
is at and the authors
show in section 6 various attacks on ad hoc constructions, but some of
them are admittedly impractical.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Unforgeable Blinded Credentials

2006-04-05 Thread Hal Finney
John Gilmore writes:
  I am aware of, Direct Anonymous Attestation proposed for the Trusted
  Computing group, .

  DAA provides
  optionally unlinkable credential showing and relies on blacklisting to
  counter credential sharing.

 Hmm, why doesn't this blacklisting get mentioned in IBM's DAA page?

They don't use that term, rather they refer to rogue TPMs.  This means
TPM keys which have been compromised in some way.  The implication is
that such keys would, once identified, be shut out from the system,
and presumably this would be done by a blacklist.

 What sort of blacklist would this be?  What actions would being listed
 on it trigger?

I don't think the operational details of this are worked out, but I
don't follow this area closely.  No doubt this is part of why none of
these systems have been fielded.  (Computers do get sold with TPMs in
them but the enormous infrastructure envisioned by the Trusted Computing
group is not in place.)

In principle, if your TPM's key got put on this blacklist, it would
prevent you from access to whatever resources require a valid TPM.
What resources those might be would depend on how and where this
technology is used, if it ever is.  But having a blacklisted TPM would
be like not having a TPM at all, in terms of access to network resources.

It may be a little more complex than this, because the DAA protocol
has a couple of different modes in which it may be used.  Rather than
a global blacklist, each TPM-requiring service might maintain its own
local blacklist of rogue TPM identifiers.  Actually I would expect there
to be both kinds of blacklists: a global one based on TPM private keys
which have been scraped and published; and a local one based on TPM
public identifiers (zeta^f values where f is the TPM private key and
zeta is a unique per-site constant) that the site decides are being used
suspiciously often, suggesting that they are being shared by a group.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Unforgeable Blinded Credentials

2006-04-04 Thread Hal Finney
Ben Laurie writes:
 If I have understood your description correctly it seems to me that this
 is defeated if, rather than sharing the master certificate, the bad guy
 allows their friend to proxy to them for whatever proofs are required.
 That way they never have to give up the precious master cert, but the
 friend's slave cert's still work.

That's a good point, proxies are another way to get around limitations on
credential sharing.  Attempts to embed sensitive secrets in credentials
don't work because there are no sensitive secrets today.  You could
use credit card numbers or government ID numbers (like US SSN) but in
practice such numbers are widely available to the black hat community.
Someone getting a credential using a stolen identifier won't be deterred
from sharing it, if the only deterrence is fear of the identifier
becoming public.

Blacklisting seems to me to be the only good solution, and in fact it
is the one proposed for the only proposed deployment of this technology
I am aware of, Direct Anonymous Attestation proposed for the Trusted
Computing group, .  This is
based on the CL signatures I referenced earlier.

Trusted Computing systems have a credential which they are supposed
to show to prove they are legit.  But if these showing instances
are linkable it is a privacy violation.  (In practice IP address is
normally going to provide just as much linkability, so for the most
part this is all political posturing IMO, but in principle this would
let you authenticate over TOR and retain your privacy.)  DAA provides
optionally unlinkable credential showing and relies on blacklisting to
counter credential sharing.  Actually the credentialed keys are supposed
to be protected by hardware, so this is a second layer of defense in
case someone figures out how to extract them from the chips.

I'm skeptical that this will actually go forward; we are all familiar
with the arguments against Trusted Computing proposals.  But it is still
of theoretical interest as a case study for unlinkable credentials which
might actually be fielded in the near future.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Unforgeable Blinded Credentials

2006-04-01 Thread Hal Finney
Ben Laurie writes:
 It is possible to use blind signatures to produce anonymity-preserving

 It seems to me quite obvious that someone must have thought of this
 before - the question is who? Is it IP free?

David Chaum did a great deal of work in this area in the 80s and 90s.
He pretty much invented the idea of anonymous credentials.  Stefan Brands
used slightly different techniques a few years later to create improved
versions.  More recently, Camenisch and Lysyanskaya have created a number
of anonymous credential systems based (roughly) on group signatures.
Some work was obstructed by the patent on the Chaum blind signature
technique, but that expired last year.  I think your basic concept is IP
free, but you should review the patents by these researchers to be sure.

 Obviously this kind of credential could be quite useful in identity
 management. Note, though, that this scheme doesn't give me unlinkability
 unless I only show each public/private key pair once. What I really need
 is a family of unlinkable public/private key pairs that I can somehow
 get signed with a single family signature (obviously this would need
 to be unlinkably transformed for each member of the key family).

There is an operational difficulty with this goal as stated.
To demonstrate it, consider a trivial way of achieving the goal.
The credential issuer creates a special public/private key pair that is
associated with the credential.  To everyone who earns the credential,
he reveals the private key (which is the same for everyone who has the
credential).  To show that he holds the credential, the key holder issues
a signature using the private key corresponding to the publicly-known
credential public key.  Now he can show credential ownership as often
as desired, without linkability, because all such demonstrations look
the same, for all members.

This illustrates a problem with multi-show credentials, that the holder
could share his credential freely, and in some cases even publish it,
and this would allow non-authorized parties to use it.  To avoid this,
more complicated techniques are needed that provide for the ability
to revoke a credential or blacklist a credential holder, even in an
environment of unlinkability.  Camenisch and Lysyanskaya have done quite
a bit of work along these lines, for example in .

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: [Cfrg] HMAC-MD5

2006-03-30 Thread Hal Finney
I (Hal Finney) wrote:
 A couple of (rather uninformed) thoughts regarding HMAC-MD5:  First,
 how could collision attacks be extended to preimage attacks?  And second,
 how would preimage attacks affect HMAC-MD5?

I have to apologize for that message; I was totally confused particularly
in the second part where I discussed the impact of an MD5 preimage break
on HMAC-MD5.  What I described was completely wrong and had nothing to do
with an attack on HMAC-MD5.  Luckily the message was so long and poorly
written that hopefully few people were able to follow it well enough to
be misled.  Again, apologies.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: [Cfrg] HMAC-MD5

2006-03-29 Thread Hal Finney
A couple of (rather uninformed) thoughts regarding HMAC-MD5:  First,
how could collision attacks be extended to preimage attacks?  And second,
how would preimage attacks affect HMAC-MD5?

For a preimage attack, consider the simplest case, a single input
block of 64 bytes.  Then Hash = IV + Compress(IV,Input).  We can try
to run this backwards: Decompress(Hash-IV,Input).  We need to choose
Input such that the result of this backwards run equals IV, the fixed
magic number that MD5 starts with.  This is the hard part.

One idea is to split the compression function into two halves:
Compress1 and Compress2, such that Compress() = Compress2(Compress1()).
Then Decompress, which is backwards, is Decompress1(Decompress2()).

We could aim for a meet-in-the-middle attack, where we would run
Compress1(IV,Input) and Decompress2(Hash-IV,Input) and try to get them to
match.  Then this value of Input would be a preimage of the desired Hash.

The problem is that Input affects both Compress1 and Decompress2 in
complicated ways.  The solution would perhaps be to aim to find a family
of Input values which caused only moderate changes to the outputs of
Compress1 and Decompress2.  This is similar to what happens now with the
hash collision attacks.  They find pairs of Inputs that have almost no
change through the various sub-parts of the compression functions.

If this could be extended so that there were not just a pair of Inputs,
but larger numbers of them that produced almost-collisions after halfway
through the compression function, then this could be a direction towards
making this MITM work.  At the most extreme case, if we could find 2^64
inputs which all collided through half the compression and half the
decompression functions, then we'd have success, we'd have a preimage
in 2^64 work.  In practice we would not reach this extreme perfection,
but perhaps we could approximate it enough that with much more work and
good ideas, a preimage could still be found with substantially less than
2^128 work.

As for the other question, the impact of preimages on HMAC-MD5: The goal
of breaking a MAC is, given a bunch of known or chosen MAC'd inputs,
but not knowing the MAC key, generate a valid MAC on a new input.
Using preimages we would aim to generate an input which matched an
output value we chose.

The structure of HMAC is to hash one block (64 bytes) of the secret
key xored a fixed repeated pad value, then the block(s) of the message.
We take the output of that hash and do it again, hashing one block of the
secret key xor a (different) fixed pad, then the output of the first hash.
This is the HMAC.

To reverse this, we would first need to invert the outer (second) hash.
The tricky part here is that the input block (after the key) has a
special form, consisting of the hash from the first step, padded per
the MD5 spec.  This padding will force fixed values (mostly zeros)
into most of the input block and only give us 16 bytes to manipulate.

So probably we would just fix the value from the input hash, fix the
IV that results from hashing the outer key block, and find the output
from this second block as the MAC value we will show an input for.
Then we will turn our attention to the first block, which is key xor pad.
We have its output value (the fixed intermediate IV we just chose) and
so we would apply the inversion algorithm to find the input.  This can
be xored with the pad to get the key.  Note that this is not the user's
key, this is just a key that works for the outer hash.

Now we do the inner hash.  We use the key we found, xor with the
appropriate fixed pad value, and hash to do the first block of the
inner MD5.  This gives us the IV for the second block, and we have
the output for that block - it is the fixed value we chose above.
We apply the inversion function again to get an Input value that

Now we have succeeded: this Input value, along with the key we found in
the first step, will produce the MAC we also found in the first step.
It is not a MAC we have seen before so we have an official break.

Therefore the ability to invert single blocks of MD5 will likely lead
to an effective break of HMAC-MD5.  Whether the current attacks against
MD5 can be advanced to that point remains to be seen.  If it works it
will certainly be one of the premier cryptographic accomplishments of
recent years.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Entropy Definition (was Re: passphrases with more than 160 bits of entropy)

2006-03-23 Thread Hal Finney
This is getting pretty far afield from cryptography but it is a topic
I find very interesting so I can't resist jumping in.

John Denker writes:
 OK, in a moment we will have gone through four plies of no-it-isn't
 yes-it-is no-it-isn't yes-it-is.  Let's get serious.  The axiomatic
 definition of a measure is
-- a mapping from sets to numbers
-- positive
-- additive on the countable union of disjoint sets

 And a probability measure has the further property of being
-- bounded above

 I have checked that -- with due attention to trivial details --
 .5 ^ (program length) satisfies this definition.  If you wish to
 renew the assertion that there is no such probability measure, please
 explain which of the axiomatic requirements is not met.  Please be

This is true, in fact it is sometimes called the universal distribution
or universal measure.  In more detail, it is a distribution over all
finite-length strings.  The measure for a particular string X is defined
as the sum over all programs that output X of 1/2^L_i, where L_i is the
length of each such program.

Often the algorithmic complexity of a string is defined as the length
of the shortest program to output the string.  The universal measure is
based on the same idea, but takes into consideration that there may be
multiple programs that output the same string.  Each program of length L_i
contributes 1/2^L_i to the string's measure.  If there is only one short
program and all others are much longer, then the probability measure
is essentially 1/2^C where C is the length of this shortest program,
i.e. the algorithmic complexity.

The universal measure for a string can also be thought of as the
probability that, given a fixed Universal Turing Machine (UTM), a randomly
chosen input program will output that string.

So this is clearly a probability distribution (with some technicalities
regarding issues of program lengths being glossed over here) as John
Denker says.  However to go from this to a notion of entropy is more

There are a countably infinite number of finite strings, and all of
them have non-zero probabilities under this distribution.  This means
that for most strings, the probability must be very low, asymptotically
approaching zero.  In fact you can show that for most strings of length n,
their measure is 1/2^n; this is equivalent to saying that most strings
are effectively random and have no shorter program to output them.

Shannon entropy is defined over a probability distribution.  That is,
given a probability distribution we can find its Shannon entropy by
summing -p_i / log2(p_i) over all members of the distribution.  If we
approximate the universal distribution by 1/2^n for strings of length
n, this sum is clearly divergent.  So there is not really a meaningful
Shannon entropy for this probability distribution, or in other words
the entropy is infinite.

John Kelsey asked:
  Indeed, what's the probability distribution of the sequence of bits
  defined by Chaitin's Omega?  

This probability distribution is defined only over finite strings and so
Omega is not within the universe of this distribution.  It should also be
noted that it is impossible for an n bit program to output more than n
bits of Omega (plus or minus an additive constant specific to the UTM).
Hence even if we consider successive approximations to Omega of ever
increasing length, their measures would tend asymptotically to zero.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Fermat's primality test vs. Miller-Rabin

2005-11-15 Thread Hal Finney
Ron Rivest reported on some theoretical and practical experimental
work in Crypto 90, Finding Four Million Large Random Primes,

A number n is a (base two) pseudoprime if it is composite and
satisfies the identity 2^(n-1) = 1 mod n  How rare are pseudoprimes?
We performed an experiment that attempts to provide an answer...

They tested 718 million random 256-bit values.  First they performed a
small divisor test using divisors up to 10^4.  43,741,404 numbers passed.
These were then tested using the equation above (the Fermat test with
base 2).  4,058,000 passed that further test.  These were then subjected
to 8 iterations of Miller-Rabin to see which were pseudoprimes.

None of them were pseudoprimes.  All of the numbers in this sample which
passed the small divisor and base-2 Fermat test passed all subsequent
MR tests and were presumably all prime.

Rivest goes on and uses a conjecture of Pomerance to argue that the
number of pseudoprimes  2^256 is at most 4 x 10^52, while the number
of true primes is 6.5 x 10^74.  Hence your chance of running into a
pseudoprime is less than 1 in 10^22.  I'm not sure the role of the
small-divisor tests but I think that may make the odds even better.
The larger primes in use today should also have improved odds.

Based on this kind of result, RSAREF, the free library available from
RSA back in the 90s, did not use MR and did not do multiple tests.
It performed a small divisor test (only testing 3, 5, 7 and 11 as
divisors!) and a single base 2 Fermat test, for its RSA keygen.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-22 Thread Hal Finney
Ben Laurie writes:
 Apologies, slightly at cross-purposes here. For a start, Sophie Germain 
 primes are needed for D-H (or rather, safe primes), and secondly, I was 
 talking about proving arbitrary primes, rather than constructing 
 provable primes.

Dan Bernstein has lots of good information on the state of the art in
general primality (and compositeness) proving. points to his recent survey paper and has
a table of the various algorithms.  Interestingly there are considerable
tradeoffs between proving time and verification time.  There are some
methods that create instant proofs but then take a long time to verify. has some of Dan's own work, including an
algorithm which creates a certificate in time quadratic in length, with
verification costing time proportional to the 4th power of the length.

He suggests that at this point the best practical algorithm is based on
elliptic curves, which is conjectured to have running time proportional
to the 4th power of length for finding proofs and to the 3rd power for
verifying them.  I don't know what the actual numbers are for prime sizes
of interest (presumably 1K-8K bits or so).  References are available
from his papers.

Several programs to implement ECPP can be found from  I don't
know about source code however.  It might be interesting to run these
over some of the Oakley primes and publish the certs - I vaguely recall
seeing something like that in an RFC.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-21 Thread Hal Finney
Ben Laurie writes:
 Related to this is a project I keep considering and never quite getting 
 around to is to include a prime proof verifier in OpenSSL. It would be 
 pretty cool to have modes which only work when all relevant primes come 
 with proofs.

 I've looked into this a few times, but have always ended up at a slight 
 brick wall: I'd like to use proofs for which there's efficient (yes, I 
 know efficient means only takes a few months to run) code to produce 
 the proofs, as well as (obviously) efficient (where efficient means 
 really fast) verifiers. This is, of course, so new proven primes can 
 be produced without having to wait for someone with proprietary code to 
 feel so inclined.

If you look at Wei Dai's Crypto++ library,, you
will see two implementations of provable prime generators, called
MihailescuProvablePrime and MaurerProvablePrime.  The first in particular
was quite fast and took only about 10 seconds to generate a 1024 bit
prime on my laptop (1GHz Mac G4).  However 2048 bit primes took more like
6 to 8 minutes, so it does slow down quite a bit for larger primes.

These functions don't output the certificate that proves it to be prime,
but they have a recursive structure and if you preserve the intermediate
values then there is a fast way of verifying the resulting primes.
The Mihailescu version is from his Crypto 94 paper which is available
from his web site, and also
discusses verification.  I googled and found a someone more recent paper
by Mihailescu,

 Oh, BTW, bonus points if the prover can be run on large numbers of 
 processors in parallel. Even more points if communication between the 
 CPUs are low bandwidth.

Unless you're looking for primes with a special format, like Sophie
Germain primes or ones with lots of 1's up front and/or in the back, or
primes considerably larger than 2048 bits, current methods should be fast
enough for most applications even on sequential processors.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Fwd: Tor security advisory: DH handshake flaw

2005-08-19 Thread Hal Finney
 - Forwarded message from Roger Dingledine [EMAIL PROTECTED] -
 In Tor, clients negotiate a separate ephemeral DH handshake with each
 server in the circuit, such that no single server (Bob) in the circuit
 can know both the client (Alice) and her destinations. The DH handshake
 is as follows. (See [1,2] for full details.)

 Alice - Bob: E_{Bob}(g^x)
 Bob - Alice: g^y, H(K)

 Encrypting g^x to Bob's public key ensures that only Bob can learn g^x,
 so only Bob can generate a K=g^{xy} that Alice will accept. (Alice, of
 course, has no need to authenticate herself.)

 The problem is that certain weak keys are unsafe for DH handshakes:

 Alice - Mallory: E_{Bob}(g^x)
 Mallory - Bob:   E_{Bob}(g^0)
 Bob - Mallory:   g^y, H(1^y)
 Mallory - Alice: g^0, H(1^y)

 Now Alice and Bob have agreed on K=1 and they're both happy. In fact,
 we can simplify the attack:

 Alice - Mallory: E_{Bob}(g^x)
 Mallory - Alice: g^0, H(1)

I was just at Crypto yesterday and Hugo Krawczyk in his talk emphasized
the difficulty of securely designing key exchange protocols.  He was
talking about implicit authorization protocols where the exponentiation
involves the long term public key(s).  This protocol is different but
there are still many ways things can go wrong.

This attack is an example of a small subgroup attack where the derived
value is forced into a small subgroup mod p, in this case the trivial
subgroup with one element.  Sometimes other subgroups can be used,
such as the group with order two (consisting of 1, p-1), or potentially
other groups.  But I checked the source code and Tor is using an Oakley
prime from RFC2409, with a generator g = 2.  The prime p is such that
q = (p-1)/2 is prime also, and g generates the prime order subgroup of
size q.  The only subgroups of such a p have order 1, 2, q, and 2q==(p-1).
By checking the received bignum is not 1, -1, or 0 (good catch, I forgot
about that one) and also not = p, you should be okay.

Oh, I just thought of another small-subgroup related attack.  Very minor,
but a leak.  Mallory lets Alice's message goes through but negates Bob's
g^y value:

Alice - Mallory: E_{Bob}(g^x)
Mallory - Bob:   E_{Bob}(g^x)
Bob - Mallory:   g^y, H(K)
Mallory - Alice: -g^y, H(K)

Now, the exchange will complete successfully only if x is even.
So Mallory learns this fact.

You also want to think about replay attacks with these protocols, but
I don't see much of an issue there.  As long as x is fresh each time
then a replay shouldn't be possible.  And if you're re-using x values
you probably have a lot more serious problems than replay attacks.

I'm not in love with publishing H(K), especially with the iffy state
of hash functions these days.  Theoretically it provides another avenue
of attack to find the key.  Granted, K is 1024 bits and H(K) only 160,
so even if H were invertable, K would still be unguessable, and we're a
long, long ways from inverting any modern hash functions.

Another way to accomplish the same thing would be to encrypt a known
value under the derived encryption key.  Since you're going to be
encrypting lots of other stuff with the key, some of which you have to
pretty much assume is going to be known plaintext, you aren't exposing
any new weaknesses by doing that.

If you do want to use a hash, it's usually a good idea to throw as much
stuff into it as you have lying around.  I would include g^x and g^y in
the hash.  This would solve the attack you're worried about right there,
because Mallory doesn't know g^x.  Probably include p and g as well,
and Bob's identity.  It may be overkill but you never know when it will
stop an attack you didn't think of.

Ideally, I think Tor should switch to a different key exchange
protocol, one which has some degree of provable security, but
I am hesitant to recommend one.  Looking at your docs I gather
that you have some pretty severe space constraints.  Your article says
that you didn't want to use a signature because you didn't have room
for it in your packet.  It also says, Preliminary analysis with the
NRL protocol analyzer [35] shows this protocol to be secure (including
perfect forward secrecy) under the traditional Dolev-Yao model.
It's interesting that these attacks exist given this security analysis.
Maybe it was treating the arithmetic as something of a black box?
Chalk it up as another example of the limitations of these kinds of tools.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Possibly new result on truncating hashes

2005-08-02 Thread Hal Finney
John Kelsey writes:
 The high order bit is that you can't generally guarantee
 that truncating your hash (chopping off some bits) won't
 weaken it.  That is, if you chop SHA256 off to 160 bits as a
 replacement for SHA1 (something I'm working on with Niels
 Ferguson for X9 right now), it's possible that there's no
 attack on SHA256, but there is an attack on SHA160.  

This is a good point, but I think the lesson is that all the bits of a
hash have to be strong, for it to be considered strong.  If you have
a 2^64 attack to find a collision in 160 bits of SHA256, then SHA256
is broken.

It should not be possible to identify any subset of k bits in the output
of a hash function, or more generally any function mapping the hash
output to a k bit result, which can have collisions found in less than
2^(k/2) work.

Whether hash functions like SHA256 can meet this standard is far from
clear, unfortunately.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Menezes on HQMV

2005-07-12 Thread Hal Finney
Eric Rescorla wrote, on July 1:
 There's an interesting paper up on eprint now:
   Another look at HMQV
   Alfred Menezes
   In this paper we demonstrate that HMQV is insecure by presenting
   realistic attacks in the Canetti-Krawczyk model that recover a
   victim's static private key. We propose HMQV-1, a patched
   version of HMQV that resists our attacks (but does not have any
   performance advantages over MQV). We also identify the fallacies
   in the security proof for HMQV, critique the security model, and
   raise some questions about the assurances that proofs in this
   model can provide.
 Obviously, this is of inherent interest, but it also plays a part
 in the ongoing debate about the importance of proof as a technique
 for evaluating cryptographic protocols.

I notice that Hugo Krawczyk has now responded by updating his HMQV paper
at  The details are a little complicated;
basicaly he agrees with Menezes about some things but disagrees on others.
However he then goes on to address the underlying issue, the nature and
use of proofs of security.

[Krawczyk writes:]

   A personal perspective. I would like to thank Alfred Menezes for
   identifying the oversight in the HCR proof and the need for group
   membership verification in the one-pass protocol. At the same time, I
   must strongly disagree with the attempt in [32] to discredit the
   effort of the cryptographic community dedicated to improving our
   understanding and design of protocols. True, we make mistakes (and I
   do not justify my own); and proofs (even if correct) are never
   stronger than the model and assumptions they are based on. But with
   all its imperfection, this form of analysis is an essential tool for
   gaining confidence in the soundness of a cryptographic design.
   Moreover, as clearly shown here, the proof process itself serves as a
   guide in choosing the right design elements.
   At a time when we demand the best (almost perfect) security from
   basic encryption and hash functions, and having witnessed the effects
   of initially-mild attacks, we can only hope that the
   applied-cryptography community and its representing standard bodies
   will see formal analysis as a requirement, and main source of
   confidence, when adopting protocols for wide use. These analyses can
   (and must) be verified by the community at large (in contrast, ad-hoc
   designs do not even provide the 'luxury' of judging well-defined
   security properties). This is all the more significant in the case of
   a protocol such as MQV which is not only intended for wide commercial
   use but also to protect 'classified or mission critical national
   security information'.

[End of Krawczyk comments]

The question of the usefulness and value of proof techniques in
cryptography will continue to be debated.  Hugo Krawczyk is going to
present his HMQV technique at Crypto next month, so perhaps there will
be additional discussion there.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Why Blockbuster looks at your ID.

2005-07-11 Thread Hal Finney
Perry Metzger writes:
 So, what is to be done? I would propose that the replacement of the
 credit card infrastructure is needed. Fraud is prevalent because of a
 massive inherent security flaw in the current system, to whit,
 the account number is identical to the payment authenticator, and
 you can make a payment merely through possession of a piece of stolen

 A system in which the credit card was replaced by a small, calculator
 style token with a smartcard style connector could effectively
 eliminate most of the in person and over the net fraud we experience,
 and thus get rid of large costs in the system and get rid of the need
 for every Tom, Dick and Harry to see your drivers license when you
 make a purchase. It would both improve personal privacy and help the
 economy by massively reducing transaction costs.

Have you ever used an ATM/debit card for a purchase?  You swipe it and
then the merchant hands you a keypad to enter your PIN.  Yes, an insider
could hack the device and steal your PIN along with your card, or use
various other attacks to get the PIN, but it's much more complicated
than using an opportunistically stolen credit card.

These have come into common use in the past several years.  I don't
understand the commentary here which seems oblivious to the existence of
this widely used alternative payment system in the U.S.  All I am reading
is oh, we can't switch, no one will ever switch from credit cards.
People are switching; it's happening everywhere.

A video game chain store in town, I think it's EBX, only accepts these
cards, they won't take credit cards.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: AES cache timing attack

2005-06-17 Thread Hal Finney
Peter Gutman writes:
 [EMAIL PROTECTED] (Hal Finney) writes:
 Steven M. Bellovin writes:
  Dan Bernstein has a new cache timing attack on AES:
 This is a pretty alarming attack.  

 It is?  Recovering a key from a server custom-written to act as an oracle for
 the attacker?  By this I don't even mean the timing-related stuff, but just
 one that just acts as a basic encryption oracle.

Does it though?  Take a look at the code at the end of Dan's paper,
server.c in Appendix A, which I have reproduced below.  It does not appear
to act as an encryption oracle.  It takes the input, which is *random*
(visible in Appendix C), encrypts it and returns the timing it took to
encrypt it.  However, it does not return the encrypted result.

The one extra piece of information it does return is the encryption of
an all-zero packet.  So there is a small element of chosen plaintext

But for all the rest, as far as I can see a passive eavesdropper on an
encrypted channel with a good timer could make it work.

Hal Finney



#include sys/types.h
#include sys/socket.h
#include netinet/in.h
#include openssl/aes.h

unsigned int timestamp(void)
  unsigned int bottom;
  unsigned int top;
  asm volatile(.byte 15;.byte 49 : =a(bottom),=d(top));
  return bottom;

unsigned char key[16];
AES_KEY expanded;
unsigned char zero[16];
unsigned char scrambledzero[16];

void handle(char out[40],char in[],int len)
  unsigned char workarea[len * 3];
  int i;

  for (i = 0;i  40;++i) out[i] = 0;
  *(unsigned int *) (out + 32) = timestamp();

  if (len  16) return;
  for (i = 0;i  16;++i) out[i] = in[i];

  for (i = 16;i  len;++i) workarea[i] = in[i];
  /* a real server would now check AES-based authenticator, */
  /* process legitimate packets, and generate useful output */

  for (i = 0;i  16;++i) out[16 + i] = scrambledzero[i];
  *(unsigned int *) (out + 36) = timestamp();

struct sockaddr_in server;
struct sockaddr_in client; socklen_t clientlen;
int s;
char in[1537];
int r;
char out[40];

main(int argc,char **argv)
  if (read(0,key,sizeof key)  sizeof key) return 111;

  if (!argv[1]) return 100;
  if (!inet_aton(argv[1],server.sin_addr)) return 100;
  server.sin_family = AF_INET;
  server.sin_port = htons(1);

  s = socket(AF_INET,SOCK_DGRAM,0);
  if (s == -1) return 111;
  if (bind(s,(struct sockaddr *) server,sizeof server) == -1)
return 111;

  for (;;) {
clientlen = sizeof client;
r = recvfrom(s,in,sizeof in,0
  ,(struct sockaddr *) client,clientlen);
if (r  16) continue;
if (r = sizeof in) continue;
sendto(s,out,40,0,(struct sockaddr *) client,clientlen);

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: AES cache timing attack

2005-06-16 Thread Hal Finney
Steven M. Bellovin writes:
 Dan Bernstein has a new cache timing attack on AES:

This is a pretty alarming attack.  Bernstein was actually able to recover
the AES key using a somewhat artificial server which reported its own
timing to do an AES operation.  In principle the same attack would be
possible on a typical remote server, using a larger number of requests
to average out timing variations.

He also had some critical things to say about the AES selection
process, which apparently dropped the ball on this issue.  Other ciphers
got dinged for nonconstant execution time, but no one thought that cache
misses would be that significant.

Dan has more information at, including
graphs showing the variability in timings for various
implementations at and, and his own attempt at a (nearly)
constant-time AES implementation as part of his poly1305-aes MAC function.

It would be interesting to see how the speed of his AES implementation
compares to that of other widely used versions like Brian Gladman's.
How much speed penalty do you pay to get the constant speed?  As Dan
notes, you can easily make a slow AES that runs at constant speed, but
a fast one is far more difficult.

I also wonder how it would compare to take something like Gladman's
(supposing it is faster than Bernstein's), estimate its worst case
running time, and then add a delay using a high-res timer from the
operating system to make it always take the same time.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: expanding a password into many keys

2005-06-14 Thread Hal Finney
Ian Grigg wrote:
 I'd like to take a password and expand it into
 several keys.  It seems like a fairly simple operation
 of hashing the concatonatonation of the password
 with each key name in turn to get each key.

The recommended technique I've seen for this (I think David Wagner
suggested it on sci.crypt years ago) is to use a MAC:

key = MAC (password, keyname)

The security property of a MAC is that you can get as many messages MAC'd
as you want, and you won't be able to guess a MAC on any new messages.
That's exactly what you want here, that an attacker can learn keys when he
knows or chooses keynames, but be unable to guess any keys for any other
keynames.  It's a good fit to the security requirements for your problem.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: [IP] SHA-1 cracked?

2005-03-05 Thread Hal Finney
Steve Bellovin writes:
 Note that finding a hash function collision  by brute force is
 inherently harder, because it requires some communication:  two
 widely-separated machines may have produced matching outputs, but
 they need to know about the other one.

That's not necessarily true, although we don't know the details yet about
the new attacks so we can't say for sure.  (The new cert collision paper
suggests that the details will be presented at Eurocrypt.)

Some of the work in this area finds the collisions in a different way
than might be expected.  They start with a linear or nearly linear
approximation to the hash function.  On this basis they find an XOR or
additive difference that will produce a collision.  Then they look for an
input for which this pre-chosen difference will produce a collision in the
actual hash.  That amounts to finding a text for which the nonlinearities
cancel out in the proper way, so that the chosen difference works to
produce a collision.

In the case of MD5, the differential was only 6 (carefuly chosen!) bits.
The hard part was to find a plaintext where the nonlinearities
associated with those bits did not prevent the collision from occuring. presents some musings on the
Wang attack and estimates that they could find a suitable text for this
differential in 2^42.2 work, which is a couple of orders of magnitude
more than what Wang apparently needs, indicating that she has more tricks
up her sleeve.

This method does not require comparing hashes from different
plaintexts.  Rather, each independent search engine is given the
pre-chosen differential and tries to find a plaintext which satisfies
the conditions that will allow a collision to occur.  A machine to do
this would be highly parallelizable and would not require any special
communication capabilities.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: SHA-1 cracked

2005-02-22 Thread Hal Finney
Ian Grigg writes:
 Stefan Brands just posted on my blog (and I saw
 reference to this in other blogs, posted anon)
 saying that it seems that Schneier forgot to
 mention that the paper has a footnote which
 says that the attack on full SHA-1 only works
 if some padding (which SHA-1 requires) is not

First, that's not quite what it says.  According to what I have seen
the language is, in reference to a pair of collisions exhibited for a
weakened SHA, Note that padding rules were not applied to the messages.

But that is irrelevant.  The padding for SHA, aka Merkle Damgard
strengthening, involves padding it up a a multiple of 512 bits, while
appending a 1 bit and a 64 bit length field.  If you have two messages
M and M' which collide without this padding, they must by definition be
a multiple of the block length.  So you add one extra block which is a 1
bit, all zeros, and then the length of M.  Now you have a legally padded
pair of SHA messages which collide.  In fact, you can add anything at
all after the blocks which collide (the same thing to both messages).
Once you have a collision it stays collided as long as the suffix
is identical.

None of the hashes exhibited by Wang et al at have the padding!  That doesn't
matter.  They are still valid collisions and can be extended or padded
any way we want while retaining the colliding property.

Presumably the text in the footnote was a reference to this fact.
Don't try to interpret it as meaning that the attack won't work against SHA.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Your source code, for sale

2004-11-06 Thread Hal Finney
Enzo Michelangeli writes:
 In the world of international trade, where mutual distrust between buyer
 and seller is often the rule and there is no central authority to enforce
 the law, this is traditionally achieved by interposing not less than three
 trusted third parties: the shipping line, the opening bank and the
 negotiating bank.

Interesting.  In the e-gold case, both parties have the same bank,
e-gold ltd.  The corresponding protocol would be for the buyer to instruct
e-gold to set aside some money which would go to the seller once the
seller supplied a certain receipt.  That receipt would be an email return
receipt showing that the seller had sent the buyer the content with hash
so-and-so, using a cryptographic email return-receipt protocol.

  You could imagine a trusted third party who would inspect the code and
  certify it, saying the source code with hash XXX appears to be
  legitimate Cisco source code.  Then they could send you the code bit
  by bit and incrementally show that it matches the specified hash,
  using a crypto protocol for gradual release of secrets.  You could
  simultaneously do a gradual release of some payment information in the
  other direction.

 But it's hard to assess the value of partially-released code. If the
 gradual transfer bits-against-cents is aborted, what is left to the buyer
 is likely to be unusable, whereas the partial payment still represents
 good value.

Actually you can arrange it so that neither the partially-released code
nor the partially-transferred ecash is of any value until the whole
transfer finishes.  For example, send the whole thing first in encrypted
form, then release the encryption keys bit-by-bit.  If someone aborts
the protocol early, the best each side can do is a brute force search
over the untransferred bits to try to find the key to unlock the data
they received.

 A more general issue is that source code is not a commodity, and
 intellectual property is not real property: so the traditional cash on
 delivery paradigm just doesn't work, and looking for protocols
 implementing it kind of moot. If the code is treated as trade secret,
 rather than licensed, an anonymous buyer may make copies and resell them
 on the black market more than recovering his initial cost, at the same
 time undercutting your legitimate sales (see e.g. the cases of RC4 and
 RC2). This can cause losses order of magnitude larger than refusing to pay
 for his copy.

That's a good point.  Maybe you could use some kind of DRM or trusted
computing concept to try to force the buyer to lock up his received data.
For source code that would be pretty difficult though, it needs to be
handled in flexible ways.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

RE: Your source code, for sale

2004-11-04 Thread Hal Finney
Tyler Durden writes:
 So my newbie-style question is, is there an eGold that can be verified, but 
 not accessed, until a 'release' code is sent?

 In other words, say I'm buying some hacker-ed code and pay in egold. I don't 
 want them to be able to 'cash' the gold until I have the code. Meanwhile, 
 they will want to see that the gold is at least there, even if they can't 
 cash it yet.

 Is there a way to send a 'release' to an eGold (or other) payment? Better 
 yet, a double simultaneous release feature makes thing even more 

I've been thinking about how to do this kind of thing with ecash.
One project I'm hoping to work on next year is a P2P gambling game (like
poker or something) using my which is a sort of play-money ecash.
You'd like to be able to do bets and have some kind of reasonable
assurance that the other guy would pay up if he loses.

In the case of your problem there is the issue of whether the source
code you are buying is legitimate.  Only once you have inspected it and
satisfied yourself that it will suit your needs would you be willing
to pay.  But attaining that assurance will require examing the code in
such detail that maybe you will decide that you don't need to pay.

You could imagine a trusted third party who would inspect the code and
certify it, saying the source code with hash XXX appears to be legitimate
Cisco source code.  Then they could send you the code bit by bit and
incrementally show that it matches the specified hash, using a crypto
protocol for gradual release of secrets.  You could simultaneously do
a gradual release of some payment information in the other direction.

If you don't have a TTP, one idea for using ecash is Markus Jakobsson's
Ripping Coins for a Fair Exchange.  Basically you withdraw ecash from
your account and in effect rip it in half and give half to the seller.
Now he gives you the product and you give him the other half of the coin.
The idea is that once you have given him the ripped ecash (torn
would be a better word because ripping means something else today),
you are out the value of the cash.  You have no more incentive to cheat,
as giving him the other half won't cost you anything additional.

(Even without ecash, a service like egold could mimic this functionality.
You'd create an escrow account with two passwords, one known to each
party.  Only with both passwords could data be withdrawn from the account.
Then the buyer would transfer funds into this account.  After receiving
the goods, the buyer would send his password to the seller.)

The problem is that if the source code you are purchasing is bogus,
or if the other side doesn't come through, you're screwed because you've
lost the value of the torn cash.  The other side doesn't gain anything
by this fraud, but they harm you, and if they are malicious that might
be enough.  And likewise you might be malicious and harm them by refusing
to give them your half of the coin even after you have received the goods.
Again, this doesn't benefit you, you're still out the money, but maybe
you like causing trouble.

Another idea along these lines is gradual payment for gradual release
of the goods.  You pay 10% of the amount and they give you 10% of the
source code.  You pay another 10% and you get the next 10% of the source,
and so on.  (Or it could be nonlinear; maybe they give out half the code
for free, but the final 10% requires a large payment.)  The idea is that
you can sample and make sure they do appear to have the real thing with
a fairly small investment.

If there is some mechanism for the seller to have a reputation (like
Advogato's perhaps, with some spoofing immunity) then the problem is
easier; the seller won't want to screw buyers because it hurts his rep.
In that case it may be reasonable to ask the buyer to pay in advance,
perhaps using the partial payment system just discussed.

These various ideas all have tradeoffs, and in general this kind of
problem is hard to solve because of the complexity of what constitutes a
successful transaction.  A reputation system helps a great deal to resolve
the issues, but opens up problems of its own.  The betting problem I
want to work on is relatively easy because there is no ambiguity about
who wins, but even then it is hard to make sure that neither party can
maliciously harm the other.

Hal F.

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Financial identity is *dangerous*? (was re: Fake companies, real money)

2004-10-21 Thread Hal Finney
James Donald writes:
 On 19 Oct 2004 at 21:30, Ian Grigg wrote:
  we already have the answer, and have had it for a decade: 
  store it on a trusted machine.  Just say no to Windows XP. 
  It's easy, especially when he's storing a bearer bond worth a 

 What machine, attached to a network, using a web browser, and 
 sending and receiving mail, would you trust? 

I would suggest pursuing work along the lines of a Virtual Machine Monitor
(VMM) like VMWare.  This way you can run a legacy OS, even Windows,
alongside a high security simplified OS which handles your transactions.
You run your regular buggy OS as usual, then hit a function key to
switch into secure mode, which enables access to your financial data.
The VMM does introduces some performance overhead but for typical web
browsing and email tasks it will not be significant.

This seems more promising than waiting for Windows to become secure,
or for everyone to switch to Linux.  I believe there are a number of
academic projects along these lines, for example the Terra project, , which uses
a hardware security chip to try to protect one VM's data from another.
I don't know if the extra complexity buys you much in this application

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Crypto blogs?

2004-10-19 Thread Hal Finney
Does anyone have pointers to crypto related weblogs?  Bruce Schneier
recently announced that Crypto-Gram would be coming out incrementally
in blog form at  I follow Ian Grigg's
Financial Cryptography blog,
Recently I learned about Adam Shostack's,
although it seems to be more security than crypto.

Any other good ones?

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Time for new hash standard

2004-09-20 Thread Hal Finney
Bruce Schneier wrote:
  Luckily, there are alternatives. The National Institute of Standards and
 Technology already has standards for longer - and harder to break - hash
 functions: SHA-224, SHA-256, SHA-384, and SHA-512. They're already
 government standards, and can already be used. This is a good stopgap, but
 I'd like to see more.

Russell Nelson suggested:

I believe this is a MAC, despite the name.  It seems to be easier to
create secure MACs than secure hash functions, perhaps because there are
no secrets in a hash, while in a MAC there is a secret key that makes
the attacker's job harder.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: potential new IETF WG on anonymous IPSec

2004-09-10 Thread Hal Finney
 The IETF has been discussing setting up a working group
 for anonymous IPSec.  They will have a BOF at the next IETF
 in DC in November.  They're also setting up a mailing list you
 might be interested in if you haven't heard about it already.

To clarify, this is not really anonymous in the usual sense.  Rather it
is a proposal to an extension to IPsec to allow for unauthenticated
connections.  Presently IPsec relies on either pre-shared secrets or a
trusted third party CA to authenticate the connection.  The new proposal
would let connections go forward using a straight Diffie-Hellman type
exchange without authentication.  It also proposes less authentication
of IP message packets, covering smaller subsets, as an option.

The point has nothing to do with anonymity; rather it is an attempt
to secure against weaknesses in TCP which have begun to be exploited.
Sequence number guessing attacks are more successful today because of
increasing bandwidth, and there have been several instances where they
have caused disruption on the net.  While workarounds are in place, a
better solution is desirable.

This new effort is Joe Touch's proposal to weaken IPsec so that it uses
less resources and is easier to deploy.  He calls the weaker version
AnonSec.  But it is not anonymous, all the parties know the addresses
of their counterparts.  Rather, it allows for a degree of security on
connections between communicators who don't share any secrets or CAs.
I don't think anonymous is the right word for this, and I hope the
IETF comes up with a better one as they go forward.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Joux attack against multipreimages

2004-09-08 Thread Hal Finney
I was looking at Joux's paper again and I noticed that he also had
some comments regarding preimage resistance.  I believe these imply a
weakness even in the construction I proposed of using a double width
hash and then collapsing the output down to single width at the end.

My argument was that if the hash output size was n bits, so the internal
width is 2n, then it would take 2^n work to find a collision on an
internal block, but that was more work than it would take to break the
hash function by brute force, hence it was not an attack.  However I
forgot that there are some problems which an n-bit hash should resist
with even stronger than 2^n force.

Specifically, the problem of finding multiple preimages, say 2^k preimages
of some fixed value, should take about 2^k * 2^n work for an ideal hash
function.  There is no shortcut beyond trying random values and seeing
if you get lucky, and for each value the chance of success is 1 in 2^n.

However, Joux shows how to do better than this.  He uses his trick
of setting up k blocks and finding a collision in each.  Even with my
double width construction that takes k*2^n work.  This gives us a 2^k
multicollision.  Now comes the new idea.  Add one more block.  Do an
exhaustive search on that block to map the output from the multicollision
to the desired hash function output, the one we are trying to find
preimages of.  That should take about 2^n work because the chance of
success for any input is 1 in 2^n, since the actual hash output size is
n bits after folding.

Now this gives us 2^k preimages.  For each of the 2^k possible choices
in the multicollision, the extra block maps us to the desired output.
We did (k+1)*2^n work and got 2^k preimages, but it should have taken
us 2^k * 2^n work.

This means that even the double-width hash construction is not as secure
as an ideal hash.  It is safe against multicollisions but not against

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: Seth Schoen's Hard to Verify Signatures

2004-09-08 Thread Hal Finney
Hi, Adam - Yes, that's interesting.  Seth Schoen's posting and
subsequent blog entries do compare his goals with hashcash and similar
stamp minting systems; where hashcash wants to make minting expensive
and verification easy, Seth's HTV signatures aim to make signing easy
and verifying expensive.

 I think maybe you have observed an additional simplification.  In my
 case I use sender chooses x randomly (actually hash output of random
 value and resource string), and computes y = x^{x^w} mod n as the work
 function (expensive operation); and z = x^w mod phi(n), y =?  x^z mod
 n as the cheap operation (verification).

 I think your approach could be applied on the encryption side too
 resulting in simpler, faster verification.  Instead it would be:

 x is random, compute y = x^{2^t+1} mod n; verify x =? y^d mod n

The main advantage here I think is that d can be precomputed.  However you
could do the same by using y = x^{2^w} instead of x^{x^w}.  Then you could
precompute z = 2^w mod phi and you would have a single exponentiation
to verify just like in my scheme.  The RSW time-lock-puzzle paper does
it this way, they use 2^w as the exponent where w is the work factor.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: ?splints for broken hash functions

2004-09-01 Thread Hal Finney
John Kelsey critiques the proposal from Practical Cryptography:
 We do not know of any literature about how to fix the hash functions, 
 but here is what we came up with when writing this book. ... Let h be 
 one of the hash functions mentioned above. Instead of m-h(m), we use 
 m-h(h(m) || m) as hash function.

 I believe this falls to a generalization of the Joux attack, as well.  (Someone may 
 have already noticed this.)  

 a.  I build a 2^{80} multicollision on h(m) using Joux' attack, requiring 80*2^{80} 

 b.  I now have 2^{80} different messages which are being hashed with the same IV.  I 
 expect one pair of them to give me a collision.  

You did 80*2^80 work to create a collision.  But you could create a
collision without all this effort in only 2^80 work, by a conventional
birthday attack.  Just ignore the internal structure and treat it as
a 160 bit hash function and you can collide in 2^80 work.  You worked
harder than you needed to, so this is not a break.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: ?splints for broken hash functions

2004-08-31 Thread Hal Finney
John Denker writes:
 Run two hash-machines in parallel.  The first one operates
 normally.  The second one puts the first block of the string
 into a buffer (bounded size!) and then proceeds to hash the
 rest of the string, starting with the second block.  At the
 end of the message, it appends the saved block to the tail of
 the message and hashes it.

 The two results are combined in some nonlinear way, perhaps
 by appending the other machine's hash onto this machine's
 input string.

To represent this pictorially, where the Bi are the input blocks:

  (IV) - B1 - B2 - B3 - ... Bk - H1
  (IV) - B2 - B3 - ... Bk - B1 - H2

then we combine H1 and H2 nonlinearly.

 The strength here comes from the idea the that you cannot
 engineer a collision in the saved block in the second
 machine until you have engineered the collision in the
 first machine, and then if you change the saved block to
 engineer a collision in the second machine you have to
 redo everything you did in the first machine.

Another attack approach though would be to fix B1, so we have
in effect:

  (IV') - B2 - B3 - ... Bk - H1
  (IV)  - B2 - B3 - ... Bk - B1 - H2

where IV' is the output of (IV)-B1.  Now we might try to find two B2
values which simultaneously collided on IV and IV'.  This will be harder
than finding two values which collide just on IV, but how much harder?

Well, probably a lot.  Finding a regular B2 collision in a perfect
160 bit hash compression function takes 2^80 work.  Finding a double
collision like this is essentially the same as finding a collision on
a double-width hash function and takes 2^160 work, enormously more.
Of course we don't know for sure that there is no short-cut attack
that exploits the weakness of the compression function to allow double
collisions to be attacked, but it certainly appears to be much harder.

If this is in fact true, how about this simpler construction?

  (IV1) - B1 - B2 - B3 - ... Bk - H1
  (IV2) - B1 - B2 - B3 - ... Bk - H2

and again combine H1 and H2.  Here we run a hash function twice in
parallel but with two different IV values.  Superficially it looks weaker
than John Denker's construction, because the blocks line up nicely, but
as I have rearranged John's construction above they may not really be that
different.  Is there an attack against this version that John's resists?

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: A splint for broken hash functions

2004-08-31 Thread Hal Finney
Bear writes:
 This construction takes slightly more than twice as
 much work and twice as much internal state as a
 conventional hash function (embrace it guys, I don't
 think there's a way around it).

H2(H1) = H1( H1(M)  xor  H1( TT( M)))

  TT denotes some trivial transformation
  (I propose swapping high and low halves
  of the first block).  H1 is a conventional
  hash function and H2 is, I believe, fully
  resistant to the Joux attack.

Keep in mind that there are two different attacks here.  One is Joux's
multicollision weakness in iterated hash functions, which is primarily
of theoretical interest.  The other is the recent work by Wang et al,
Joux, and Biham which shows genuine attacks on weakened and full versions
of presently-used hash functions.

I think John Denker's suggestion was originally intended to make the
class of practical attacks harder, by requiring them to solve two
problems at once which interact with each other.  Then he showed how
to accomplish this while allowing incremental hashing, and indeed that
construction appears to resist the Joux multicollision attack as well.
It is that multicollision attack that we are focusing on here.

I would suggest a further generalization of your approach:

Hash ( Hash1(M) || Hash2(M) )

where Hash1 and Hash2 are different n-bit hash functions, and the outer
Hash() takes a 2n-bit input to an n-bit output.  As I suggested in my
previous mail, I propose that Hash1 and Hash2 can be as similar as SHA-1
with two different IV's.

This model captures John Denker's idea, yours above, as well as my
suggestion in the previous mail.

It is somewhat ironic to propose this, since Joux's paper had two
main results: first, that iterated hash functions have too many
multicollisions; and second, that as a result, parallel iterated hash
functions are no stronger than the individual components.  Yet here I
have proposed exactly that construction, parallel iterated hash functions
in the form of Hash1 || Hash2.  The difference is that I don't try to
get 2n strength out of it, I accept that it has only n bits of strength,
and in fact collapse it down to n bits to make that explicit.  So I have
used Joux's forbidden construction to avoid Joux's attack.

That it avoids his attack is seen as I argued before:

  (IV1) - B1 - B2 - B3 - ... Bk - H1
  (IV2) - B1 - B2 - B3 - ... Bk - H2

The state functions that chain between the blocks will be different
between the two lines, hence a block collision on one line will not be
a collision on the other and Joux's multicollision construction will
not work.  The exception would be if a collision between the lines can
be found, so that the top and bottom state functions become identical
at some point.  From that point on, the subsequent blocks can collide
on both lines and the multicollision construction could work.

To find such a collision between the lines we must find a block which
maps two different chaining inputs to the same output.  But a random
compression function with two chaining inputs is like two different
random functions.  So we must find an input which causes two different
n-bit random functions to collide.  The chance of this happening for
any input is 1/2^n so it will take about 2^n work to find one.  This is
the work necessary to find a collision between the lines.  This level of
work is greater than that needed to invert the overall hash construction
hence does not represent an attack.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: How thorough are the hash breaks, anyway?

2004-08-31 Thread Hal Finney
Dan Carosone wrote:
 There is one application of hashes, however, that fits these
 limitations very closely and has me particularly worried:
 certificates.  The public key data is public, and it's a random
 bitpattern where nobody would ever notice a few different bits.

 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.

A more likely attack along these lines would be to create two certificates
which collided and had identical keys but different identification
information or other attributes.  If you could create a situation
where a cert on collided with one on,
you could easily get the second one certified, and the signature on
it would also validate when you substituted  Presto,
you could successfully masquerade as Microsoft.

This is a collision attack rather than a second preimage attack as you
propose and so should be far easier to mount.

The attack requires being able to predict the exact form of the cert,
including validity dates and serial number.  The latter is chosen by
the CA and depending on its policies, may be easy or hard to predict.
The name serial number suggests a degree of sequentiality and some
CAs may follow such a policy, which could allow a motivated attacker to
predict the value with considerable accuracy.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: More problems with hash functions

2004-08-28 Thread Hal Finney
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: More problems with hash functions

2004-08-28 Thread Hal Finney
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 .
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.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: More problems with hash functions

2004-08-26 Thread Hal Finney
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 concrete terms, you have a message of n blocks, p1 through pn.
 you xor each block with a value computed by a nonlinear function
 from its sequence number to get q1 through qn.  Now rearrange
 q1 through qn by imposing a total ordering on p1 through pn: for
 example if p4 sorted before p7, you put q4 in front of q7.
 Finally, you compute the hash value on the blocks q1 through qn
 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.

The attacker could choose an ordering of the blocks ahead of time, and
find collisions which preserve that order.  Specifically, he can start
searching for collisions in the first one, which WOLOG we will call q1.
He can continue to search until he finds a collision which puts p1 into
the first 1/k of block address space, which will guarantee that this
block will sort first.  This will increase his work by a factor of k^2
(because only 1/k of the time will he get lucky, for each of the two
blocks in the collision).  Then he can find a collision in q2 which
puts p2 into the 2nd 1/k of block-address space, guaranteeing that p2
will sort as the second block.  Again this increases the work by k^2.
Proceeding down the line he produces a collision which leaves the blocks
in his pre-chosen order, at a cost of k^2 more work.

Joux shows that finding an 2^k collision takes k times the work to
find a single block collision.  Among other things he shows how this
reduces the work to find a collision in the output of two independent
n-bit hashes from 2^n to n*2^(n/2).  Your approach effectively makes
this (n^3)*2^(n/2) which is an improvement, but still not attaining
the exponential security increase expected from ideal hash functions.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: More problems with hash functions

2004-08-24 Thread Hal Finney
Jerry Leichter writes:
 It strikes me that Joux's attack relies on *two* features of current
 constructions:  The block-at-a-time structure, and the fact that the state
 passed from block to block is the same size as the output state.  Suppose we
 did ciphertext chaining:  For block i, the input to the compression function
 is the compressed previous state and the xor of block i and block i-1.  Then
 I can no longer mix-and-match pairs of collisions to find new ones.

Here's how I understand what you are suggesting.  Presently the hash
compression function takes two inputs: a state, and an input data block.
For SHA-1 the state is 160 bits and the input data block is 512 bits.
It outputs a state-size block of 160 bits, which gets fed into the
next block:

IV  ---  COMP   ---   COMP   ---   COMP   ---  Output
   ^ ^ ^
   | | |
   | | |
 Block 1   Block 2   Block 3

I think you are proposing to increase the output of each block by 512
bits in this case, so as to provide some data that can be xored into
the input data block of the next stage, a la CBC:

IV  ---  COMP   ---   COMP   ---   COMP   ---  Output
   ^  \  ^  \  ^
   |\-- X\-- X
   | | |
 Block 1   Block 2   Block 3

By itself, adding an xor step doesn't do anything.  The attacker would
still have full control of the output of the xor, since he has full
control of one of its two inputs.  So I think it is more appropriate to
merely think of the compression function block as taking a wider state
input from the previous stage, and not specify how the input data block
is mixed with the previous state.

This might lead to a construction in which the state passed from block
to block is, say, 512 bits, rather than 160.  The compression function
still takes two inputs, the state and the input block, and now produces
a 512 bit output.

IV  ===  COMP   ===   COMP   ===   COMP   ---  Output
   ^ ^ ^
   | | |
   | | |
 Block 1   Block 2   Block 3

(Here, the == are meant to depict wide paths.)

For the final output of the hash, we would presumably derate the
output of the last stage down to 160 bits and not claim the full 512
bits of security.  If we didn't do this step, then the construction is
precisely SHA-512 and Joux's attack still applies.

This approach does appear to defeat the Joux attack.  Finding a collision
in a sub-block which takes a 512 bit input to a 512 bit output will take
2^256 work rather than the 2^80 in the SHA-1 compression function.
So you will never find a multicollision in less work than this.  And the
most strength SHA-1 can provide against anything is 2^160 since that
it what it takes to invert it.  Since 2^256 is greater than 2^160,
the construction is strong against this attack.

We can also see from this analysis that making the paths 512 bits wide is
overkill; they only need to be twice the claimed hash strength, or 320
bits wide in this case.  Or in other words, if we took SHA-512 and only
claimed it to have 256 bits of strength, it would avoid the Joux attack.

However, the problem with this construction is that the inner blocks
now genuinely need to have 512 bits of strength, and that may not be
that easy to provide.  SHA-512's compression function does claim to have
that amount of collision resistance, but it is difficult to analyze such
strong claims, and adding this much strength may make for a slow hash.

Plus, given that we have managed to create a block with 512 bits of
security, it seems a shame to throw away half of the strength to produce
an output that avoids the Joux attack.  I think cryptographers will look
harder to try to find a way of combining sub-blocks which will retain the
strength of the individual pieces rather than throwing half of it away.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: More problems with hash functions

2004-08-24 Thread Hal Finney
Jerry Leichter writes:
 Joux's attack says:  Find single block messages M1 and M1' that collide on
 the blank initial state.  Now find messages M2 amd M2' that collide with
 the (common) final state from M1 and M1'.  Then you hav four 2-block
 collisions for the cost of two:  M1|M2, M1'|M2, and so on.

 But even a simple XOR breaks this.  M1 and M1' have the same hash H, but the
 state being passed is now very different:  H,M1 in one case, H,M1' in the
 other.  So M1|M2 and M1'|M2 are completely different:  Both started the second
 step with the compression function in state H, but the first compressed
 M1 XOR M2, and the second M1' XOR M2.

Okay, I misunderstood your earlier suggestion.  Sorry.  Rereading it:

 Suppose we
 did ciphertext chaining:  For block i, the input to the compression function
 is the compressed previous state and the xor of block i and block i-1.  Then
 I can no longer mix-and-match pairs of collisions to find new ones.

It sounds like you're saying that that the input to the second compression
function should be M1 XOR M2 instead of just M2.  Like this:

IV  ---  COMP   ---   COMP   ---   COMP   ---  Output
   ^ ^ ^
   |/-- X/-- X
   |  /  |  /  |
 Block 1   Block 2   Block 3

But this is easily compensated for: if you wanted the input to the
2nd compression stage to be M2, you'd just input M1 XOR M2 instead.
Then when this gets XOR'd with M1, M1 will will cancel out in the XOR
and you'll have a nice clean M2 going into COMP, just as you wanted.

So if you found a compression-function collision starting with IV on M1
and M1', and you found a collision starting with the common output of
that stage on M2 and M2', your four collisions would be:

M1 || (M1 xor M2)
M1 || (M1 xor M2')
M1' || (M1' xor M2)
M1' || (M1' xor M2')

In each case the actual input to the 2nd block compression function
(after xoring with the first block input) would be M2 or M2', as desired.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: On hash breaks, was Re: First quantum crypto bank transfer

2004-08-24 Thread Hal Finney
Joe Ashwood writes:
 Except for RIPEM there were known to be reasons for this, MD5 was 
 known to be flawed, SHA-0 was replaced because it was flawed (although 
 knowledge of the nature of the flaw was hidden). Even with RIPEM (and SHA-1 
 for the same reason) I have plans in place (and have had for some time) the 
 move away from 160-bit hashes to larger ones, so the attack on RIPEM had 
 little effect on me and my clients...

A minor terminology correction: the hash is RIPEMD, the more recent (and
still unbroken) version being RIPEMD-160.  RIPEMD is the RIPE Message
Digest, where RIPE is the EU's RACE Integrity Primitives Evaluation
project, and I haven't been able to find out what RACE stands for.

RIPEM was an old implementation by Mark Riordan of the PEM (Privacy
Enhanced Email) standard which preceded S/MIME.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

Re: RPOW - Reusable Proofs of Work

2004-08-21 Thread Hal Finney
Matt Crawford writes:
 If you think of POW as a possible SPAM mitigation, how does the first 
 receiving MTA assure the next MTA in line that a message was paid 
 for?  Certainly the mail relay doesn't want to do new work, but the 
 second MTA doesn't know that the first isn't a spambot.

The first MTA would exchange the received RPOW for a new one of equal
value, and pass it along with the message to the next MTA in line.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

  1   2   >