2
$\begingroup$

I am going through the Lamport Diffie One-time signature. I am having a hard time understanding

  1. How can long messages (greater than 100 bits) can be mapped into short messages (100 bits) by a one way function and only the short message signed? Can someone explain this with an example?(Refer page no.13 in attached document.)

  2. "the message can be encrypted with a newly generated random key by the signer before it Is signed, and the random key appended to the message. The signed message will therefore be random (assuming that encryption with a random key will effectively randomize the message, a fact that is generally conceded for modern encryption functions [11]). These steps will satisfy the conditions for property 2. We can therefore assume, without loss of generality, that all messages are a fixed length, e.g., 100 bits" Can someone explain this to me? (Refer page no.13 - no.14 in attached document.)

  3. "The method as described thus far suffers from the defect that B can alter m by changing bits that are 1's into D's. B simply denies he ever received xj ' (in spite of the fact he did). However, D's cannot be changed to 1's. Lamport and Diffie overcame this problem by signing a new message m', which is exactly twice as long as m and is computed by concatenating m with the bitwise complement of m. That is, each bit m. in the J original message is represented by two bits, mj and the complement of m. in the new message m'. Clearly, one or the other J bit must be a O. To alter the message, B would have to turn a 0 into a 1, something he cannot do." Can someone explain how this fixes the problem. (Please refer page no. 14)

I am trying to read up on technology around the crypto space right now. I started with the attached paper because it was mentioned in here. If you feel there are resources that explain the attached paper in detail but in a way a beginner would understand I would greatly appreciate it.

$\endgroup$

1 Answer 1

3
$\begingroup$

I am going through the Lamport Diffie One-time signature.

As a side note; this work is an early effort that culminated in what is known as "Stateful Hash Based Signature Methods"; modern designs include XMSS and LMS, and are surprisingly close to what's in the Merkle paper. You may find the Wiki link more approachable...

In any case, to address your questions:

  1. How can long messages (greater than 100 bits) can be mapped into short messages (100 bits) by a one way function and only the short message signed?

Not to sound overly simplistic:

  • We take the long message to sign

  • We use that as input to a 'one way function' (modern terminology: a hash function), which generates a fixed sized output (in this example, 100 bits)

  • We take that 100 bit output, and apply the signature algorithm to it.

This is not specific to hash based signatures; essentially all signature algorithms (at least, any I've heard of) use a variant of this as a first step. The only difference is that 100 bits would not be considered sufficiently long; we generally insist on much longer hash outputs (because the attacker's capabilities have grown greatly since 1979, hence we need to make our systems stronger).

The nonobvious question is "why is this secure"? Well, if we assume that the attacker cannot find another message that the one-way function maps to the same 100 bits, and the attacker cannot generate a signature for that different set of 100 bits that the attacker's message maps to, then it is safe.

Actually, in practice, we worry about collision attacks, where the attacker has control over the valid message being signed (but he still needs to produce a forgery, that is, a valid signature for a message that was not signed); Merkle does consider that, however lets keep things simple for now.

  1. "the message can be encrypted with a newly generated random key ... " Can someone explain this to me?

Well, this part can probably be skipped - this is one section of the paper that modern crypto doesn't follow.

Merkle tries to define a 'certified encryption function', and uses specific assumptions to do so, including a randomized input; message being signed are not randomized, and so he inserts an encryption function (with a random key) to make it match his assumptions.

In modern crypto, we don't do this - we generally use an off-the-shelf hash function (such as SHA-2 or SHAKE) and use that - those have been designed (and cryptanalyzed) to meet the various assumptions for cryptographic hash functions; hence we (as a signature designer) don't have to worry about that.

To be fair to Merkle, this may be the very first time anyone has tried to work out what a 'collision-resistant hash function' would look like, and he made a fairly decent attempt - it's just not the direction later cryptographers took it.

  1. "The method as described thus far suffers from the defect that B can alter m by changing bits that are 1's into 0's..." Can someone explain how this fixes the problem.

Well, let us consider the simplest case; signing a single bit. In the "method described thus far", to generate a private key, we'd pick a random value $x$, and apply a random function $F$ to it, generating the public value $F(x)$. Then, to sign a '1' bit, we would produce as a signature $x$ (which the the verifier would be able to validate that $F$ maps that to the public key). However, to sign a '0' bit, we wouldn't reveal anything. It is obvious that someone who sees the valid signature of '1' could convert it into a signature of '0' (or, for that matter, generate a signature of '0' without seeing anything).

In the Lamport scheme, to sign a single bit, we generate two random values $x$ and $x'$, and publish as a public key the values $F(x)$ and $F(x')$. To sign a 0, we produce $x$; to sign a 1, we produce $x'$; someone with the signature of 1 cannot generate a signature of 0 (because they'd have to produce $x$, and they don't know that).

Now, this works, however it is quite expensive (you end up needing a public key that has twice as many hash outputs as bits your hash function produces - for example, if your hash function outputs 100 bits, this has a public key that consists of 200 hashes). The paper does go on to show ways to reduce it, as mentioned in sections 4 and 5 of the paper (which are what is used in practice).

$\endgroup$
7
  • $\begingroup$ First of all thank you so much for responding and for your effort. I was down about not being able to understand the content in the paper and your response made my day and gave me hope! $\endgroup$
    – redd
    May 3 at 6:09
  • $\begingroup$ In response to your first answer. My understanding of the signature algorithm is that for every bit in the message that is transmitted there is a secret key and a public key associated with it. What I mean by every bit is that(using the example mentioned in the attached paper) is that lets say I would be selling a stock each bit in the message will tell party B which stocks to sell. If we map the message to a new 100-bit hash(referring to your example) how will party B know which stocks to sell? Because the original message is transformed to this new 100 bit-hash. $\endgroup$
    – redd
    May 3 at 6:10
  • 1
    $\begingroup$ @redd: point 1: the signature is there to allow people to verify the message, it is not there to transmit it. It is assumed that B is sent a copy of the message along with the signature. $\endgroup$
    – poncho
    May 3 at 13:21
  • 1
    $\begingroup$ @redd: a "collision resistant hash function" is not one where there are literally no two inputs that hash to the same value (it is easy to show that, for any such function, the output is at least as large as the input). Instead, it is one where it is too hard (we don't know how to do so with the resources we have) to find two different values that hash the same. $\endgroup$
    – poncho
    May 3 at 13:23
  • 1
    $\begingroup$ @redd: point 3: the point of a signature is there to allow that the message was sent, exactly as is, by A. It's not there to prevent B from claiming he didn't receive it; it's there to prevent B from claiming that A send a different message (and someone other than A from sending B a different message) $\endgroup$
    – poncho
    May 3 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.