Fan et al. Recovering MSD's

user16910689

2/21/24, 2:36 PM

I have been trying to understand the method of recovering the MSD of the nonce proposed by Fan et al. (section 4.2), in their attack targeting wNAF implementation for scalar multiplication in the OpenSSL implementation of ECDSA. They assume that the value of $L_0$ is known. I can see that using Flush+Reload, one obtains $L_{AD}$ - but (why) does this also hold for $L_{0}$?

1 + 1

side-channel-attack

fgrieu

2/21/24, 2:40 PM

Clarification: In the context, MSD stands for Most Significant Digit for a Windowed Non Adjacent Form of a secret scalar.

Score:2

Crypto

Daniel S

2/21/24, 3:46 PM

In the paper $L_0$ is the length of the binary string that represents the secret scalar multiple. In good cryptographic implementations, this secret will be selected uniformly at random from the group order. In the case of the secp256k1 curve for example, the group order is very close to $2^{256}$ meaning that roughly 50% of the time $L_0=256$. One can either consider this an attack that works 50% of the time or alternatively exhaust over the first few most likely values of $L_0$. For example, repeating the attack for the guessed values $L_0=256, 255,\ldots,247$ would work for roughly 99.9% of secret scalars.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Fan et al. Recovering MSD's

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.