Re: hash recursion shortcut impossible?

David Eather wrote:
Kristian Gjøsteen wrote:
Bernhard Kuemel <bernhard@xxxxxxxx> wrote:
rh(random number) is supposed to be data that is determined now, but
only known in the near future. It must not be known too early.

I've seen a paper on something similar, I seem to recall that David
Wagner
was one of the authors, but I don't remember the title or anything else.

Their construction was to compute x^y mod n, where n was an RSA modulus
and y was a laughably large number. The point is that whoever knows
the factors of the modulus can compute x^y much much faster than someone
who only knows the modulus and x.


http://www.eecs.berkeley.edu/~daw/papers/timelock.ps

Interesting. In my case the secret mustn't be known to the parties
involved, though. But thinking about this method I got an idea which
solves my problem without having to waste CPU cycles:

Everyone picks a big secret random number and publishes it's hash. This
determines the result. Then everyone publishes the numbers. The result
is the hash of the numbers concatenated. This is also much quicker than
wasting CPU cycles, which is preferable.

This approach is, however, vulnerable to hash collisions. One might find
two (or more) numbers yielding the same hash, publish the hash and later
may choose to publish any one number and thus influence the result after
it supposedly is already determined.

I'm afraid using encryption instead of hashes will suffer the same problem:

Everyone picks a big random number and a random key and publishes
encrypt(number,key). Then everyone publishes the number and the key. The
result is again the hash of the numbers concatenated.

Again someone might find several number/key pairs yielding the same
ciphertext. OTOH it should be much harder if the length of the number
increases, right?

So how about this:

Everyone picks a secret (but nevertheless symmetric) key and publishes
encrypt(plaintext,key), where plaintext is publicly known, e.g. 1000
binary zeros. Then everyone publishes their key and the result is the
hash of the keys concatenated.

Hmm, still open to a known plaintext attack. A party might find the keys
of the already published ciphertexts and so know the result before
publishing his ciphertext. Better keep the plaintext random and secret, too.

Thanks.
.

Relevant Pages

  • Re: Cryptographic hash function for small microcontroller
    ... The microcontroller is fairly fast ... SHA-1 and related hashes all require too much RAM for this ... <Then you can't have a cryptographic hash. ... microcontroller) to a PC using a shared secret. ...
    (sci.crypt)
  • Re: AES as hash function and PRNG
    ... > For encryption I decided to use AES-128. ... And they have to remain secret. ... If you have less than 16 bytes to hash, just pad the key with ASCII ... Choose any input as the plaintext to run through AES. ...
    (sci.crypt)
  • Re: Algorimic Complexity Attacks
    ... For instance, in a hash table, the performance is ... while using a keyed hash function offers the best ... It requires that a cryptographically random secret is used ... Now the promised attack on using a keyed hash function with the above ...
    (Bugtraq)
  • Re: CRC as authentication?
    ... |>instead of the more expensive universal hashes that require field ... If the polynomial is secret, and if you use the CRC correctly, ... | conditions on how you use it, then the resulting hash is an AXU-2 hash. ... If the attacker can force *almost* the same message to be transmitted ...
    (sci.crypt)
  • Short string of data as input of SHA 256
    ... concatened with 24 non secret bits of data, ... I obtain a 256 bits string. ... Toward an attack trying to find the input from the output is brut ... although hash algorithms are usually ...
    (sci.crypt)
Quantcast