5
$\begingroup$

I was (trying to) read the following paper: https://eprint.iacr.org/2015/673.pdf

Page 2 says:

A related attack is to replace a point P with P + T, where T lies in a small subgroup. If the user multiplies by a scalar s, they will get sP + sT instead of sP, where the difference sT gives away the low-order bits of s. Therefore, it isn’t always enough to reject points in the small subgroup.

I don't fully understand the attack. Looks like there's a protocol where the attacker, instead of sending a point P, it sends P+T where T is a point in a small order subgroup.

The other side will do s.(P+T)=Q, where technically Q=sP+sT. As an attacker, I got a the point Q, which I know is sP+[0..n-1].T for some "small" n which is the order of the small subgroup.

What I, as an attacker, should do with Q then? Try to subtract all possibilities of [0..n-1]T and see when the resulting point is part of subgroup generated by P? In theory the found i in [0..n-1] should leak s mod n.

Two questions:

  1. Is my "logic" correct on how the attacker can do this attack?
  2. This can leak some bits of s, let's say 4 least significant bits. But, why is that a problem? If s is 256 bits, I'm a bit stuck anyway as an attacker. Or is there a way to keep leaking other bits?
$\endgroup$

1 Answer 1

4
$\begingroup$

You're correct. Guess and check subtraction works, alternatively you can multiply by 8 then 1/8 to get back the original point minus the small order component and subtract. (note:for cofactor=8)

cv = Curve.get_curve('Ed25519')

#generator for low order group G
single=cv.decode_point(base64.b16decode(b'26E8958FC2B227B045C3F489F2EF98F0D5DFAC05D3C63339B13802886D53FC05'))
inv8=modinv(8,cv.order)
lo_list=[(cv.generator+single)*i-cv.generator*i for i in range(8,16)]
def get_lo(X):
    #get the low order group information from a point
    X_lo=X-X*8*inv8 #isolate LO info
    return lo_list.index(X_lo) #find it in the list

Notice that to generate the list I had to get around the checks for equality to the 8 small order points by including G.

This leaks the 3 least significant bits of the scalar which doesn't get you the key by itself.

Attacks

Getting the rest of the key requires that the victim manipulate the scalar in some way before multiplication to get information on higher bits. If the victim is willing to add or multiply by an attacker supplied value prior to multiplication then the full scalar can be recovered.

One scenario in which this could occur is if the victim expects keys to be derived from their public key (EG:K_derived=v*K_p) and the attacker can supply the v used. This can be done for privacy reasons (the derived keys can't be connected to the original key).

In the context of zero knowledge proofs the point could be multiplied by some value correlated with secret information. In schnorr signatures, leaking bits of the randomly chosen scalar can reveal bits correlated with the key and done enough times the attacker can reassemble the whole key. This attack doesn't apply there but can apply in other complex multi-round zero knowledge proofs.

Attack demo

Here's some attack code that implements this attack.

Curve25519 keys are clamped to prevent this. The scalar domain is close to 2^252. Scalar clamping clears the lowest three bits, sets bit 255 and clears bit 256. The result is of the form 8*(2^252+X) where 2^252 > X ≥ 0. The 2^252 is there to mitigate side channel attacks in stupid implementations.

scalars of the form 8*X implicitly clear the small order component when multiplying. A scalar can be converted to this form by multiplying by inverse(cofactor) and then multiplying by the cofactor without reducing modulo the group order.

Point cannonicity

another problem with the low order part of points is that equivalent points that differ only in their low order component are ... well ... different. In CryptoNote based cryptocurrencies this led to a double spend vulnerability since implementations expected that equivalent public keys would have the same byte representation but they discarded cofactor information.

$\endgroup$
2
  • $\begingroup$ Thanks a lot for your comprehensive answer! I'm not that sure I understood the "Point cannonicity" correctly. For example, if the cofactor is 8, since they did the 8*X trick then in theory you can have up to 8 secret keys that would lead up to the same public key; and somehow that lead to a security problem? $\endgroup$
    – Enthusiast
    Commented May 21, 2023 at 22:31
  • $\begingroup$ jonasnick.github.io/blog/2017/05/23/… If I understand it correctly, the blockchain used some sort of structure where there was an easy way to prove set membership of a given key, and had a rule (keys only get used once). So a transaction puts a key into the set and a later transaction uses that key to spend the output, after which it can't be used again. Of course if there are 8 equivalent keys with different representations the one time use rule can be broken and outputs can be spent more than once. $\endgroup$ Commented May 22, 2023 at 1:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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