Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am currently experimenting with ed25519 and I noticed that on secret key creation, bit 254 is always set and the lower 3 bits are always cleared. I found that bit 254 is always set to protect against timing attacks in this question: When using Curve25519, why does the private key always have a fixed bit at 2^254?

But why are the lower 3 bits cleared. Obviously it has to do with the formula in the curve25519 paper: The set of secret keys is defined to be $\{\underline{n} : n \in 2^{254} + 8\{0, 1, 2, 3,\ldots, 2^{251}-1\}\}$

It's because of the 8 in there, but why is that 8 there? I suspect it has something to do with theorem 2.1 in the curve25519 paper, but I am not sure, because I do not understand fully what is being proven there.

I am experimenting with ed25519 primitives in some cryptographic routines which need me to add scalars to the secret key (add secret keys). Even if I add two well formed ed25519 secret keys, the result will not always have bit 254 set and the lower 3 bits cleared. Is this a security problem? I understand the risk for bit 254 but not the lower 3.

share|improve this question
3  
The group order is a multiple of 8. Setting the lowest bits zero, sets the scalar to a multiple of 8, ensuring that the points are in the prime-order subgroup without the small subgroup interfering. –  CodesInChaos Dec 18 '13 at 13:23
1  
Just to add to the above comment: This means you don't have to verify that strings represent group elements, which is typically costly. Protocols that omit this step without other countermeasures have been broken. –  K.G. Dec 18 '13 at 15:01
    
Please take into account that I only have a basic understanding of ECC when I ask: According to the paper, the group order of ed25519 is a prime ( $ 2^{252} + 27742317777372353535851937790883648493$ ) which by definition is not a multiple of anything. What am I missing? Also, I am looking for the implications for when I add / multiply 2 valid secret keys, I get a non multiple of 8. Does this mean this new secret key is unfit for signing messages with edDSA? –  MepAhoo Dec 19 '13 at 13:49
1  
Answering my own questions: It seems there are 2 groups at play here. The group of the curve and the group of the generating base point. In this case the curve group is 8 * the base point group. The problem with this is descibed in the small-subgroup attack section of this link: safecurves.cr.yp.to/twist.html . Curve25519 solved this problem by making every secret key a multiple of 8. Although it seems to me this sacrifices 3 bits to prevent a 3 bit security issue. An alternative is to check the public keys before processing them, as described here: cr.yp.to/ecdh.html#validate –  MepAhoo Dec 23 '13 at 13:12

1 Answer 1

up vote 9 down vote accepted

Clearing the lower 3 bits of the secret key ensures that is it a multiple of 8, which in turn ensures that no information, small as it may be, about the secret key is leaked in the case of an active small-subgroup attack.

The typical simple Diffie-Hellman key exchange works like this:

$$ \text{Alice} \xrightarrow{\hspace{3cm} a G \hspace{3cm}} \text{Bob} \\ \text{Alice} \xleftarrow{\hspace{3cm} b G \hspace{3cm}} \text{Bob} $$

$a$ and $b$ are Alice and Bob's secret keys, and $G$ is the base point, which is $(9,\ldots)$ in curve25519. Alice computes $a\cdot bG$, Bob computes $b \cdot aG$, and the shared secret is derived by passing $abG$ through some key derivation function.

Now, as you have noticed, the order of $G$ is $p_1 = 2^{252} + 27742317777372353535851937790883648493$, whereas the number of points in the curve itself is $8 p_1$. This means that there are a few remaining points that have small order. An active attacker can, e.g., replace Bob's message $bG$ with a point of order $8$ and be able to find $a \bmod 8$ by inspecting following messages. When every valid secret key is $0 \bmod 8$, the attacker gets nothing.

One may argue that this wastes 3 perfectly good key bits to prevent an already ineffective attack. Notice, however, that the actual security of the scheme is tied to the order of the base point, $p_1 \approx 2^{252}$. Clearing those 3 bits (out of 255) does not reduce the keyspace since it still leaves 252 useful bits, giving roughly the same keyspace as the number of points generated by $G$.

share|improve this answer
    
I kind of figured this out above, but your answer is the most complete and easy to understand for me. Also you answered the "are 3 bits wasted?" question I pose later. Thanks –  MepAhoo Jan 1 at 15:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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