#StackBounty: #elliptic-curves #threshold-cryptography Is this distributed random oracle scheme safe?

Bounty: 50

This question comes from an issue raised in another question: Non interactive threshold signature without bilinear pairing (is it possible)?

Is the proposed random oracle model safe when trying to output a distinct and random $m times G = M$ value?

Doing the interpolation for $t$ compromised shares $m^{‘}i$ results in: $l_0 times M_0 + sum^t{i=1} l_i cdot m^{‘}i times G = m times G$ that reduces to $(m – sum^{t}{i=1} l_i cdot m^{‘}_i) cdot l^{-1}_0 times G = M_0$, where $M_0$ is always different for each signature. So, I suppose we can’t reuse previous values to perform the attack.

How do you solve to a wanted $m$ value without resolving the DLP? Searching for $m^{‘}_i$ and $m$ for some unknown $m_0$ is brute forcing the DLP, even in the k-sums context!

What I have seen in the k-sums/generalized birthday problem is a way to solve for $x_1 oplus … oplus x_n = 0$. Mapping this approach to our problem, we should try to solve for $x_1 oplus … oplus x_n = m_0$ equivalent to $x_1 oplus … oplus x_n oplus m_0 = 0$. The issue is, $m_0$ has a specific value but it is unknown to the solver due to DLP. How can we solve for something we don’t know? If such solution were possible, won’t this be solving the DLP?

I need a math clarification to explain exactly how this attack is performed?

Get this bounty!!!

#StackBounty: #elliptic-curves #signature #dpa #fault-attack Protecting Ed448 against DPA and fault attacks

Bounty: 50

There are some papers (1, 2) describing fault attacks in EdDSA. One suggested countermeasure is to add randomness to the input of the first hash call, which outputs a scalar.

This paper describes a DPA attack against EdDSA, and suggests a similar countermeasure. However, the randomness must be placed in a specific place:

This can be achieved by padding
the key with fresh random bits such that the first 1024-bit block is composed
only by key and random value, without any bits known to the attacker.

Following their notation, that would mean changing $H(b,M)$ to $H(b,Z,M)$ where $Z$ is the random padding such that the length of $b || Z$ is equal to the block size of the hash.

However, consider Ed448, as defined in RFC 8032 (the issue I’ll talk about would also apply to Ed25519ctx and Ed25519ph, but I’ll use Ed448 as an example). In the Sign operation, the hash call is SHAKE256(dom4(prehash, context) || b || PH(M), 114). Prehash is a flag indicating Ed448 or Ed448ph. Context is an optional context string. The dom4 function is:

dom4(x, y): The octet string "SigEd448" || octet(x) || octet(OLEN(y)) || y, where x is in range 0-255 and y is an octet string of at most 255 octets. “SigEd448” is in ASCII (8 octets).

Now, my question is: what is the proper way to add the DPA countermeasure to Ed448? (And Ed448ph, Ed25519ph, Ed25519ctx)?

My first guess would be to use SHAKE256(dom4(prehash, context) || b || Z || PH(M), 114), with Z being enough bytes to fill the SHAKE245 block size. However, if the context is used, then Z could get too small. Also, the paper states that the first block must be “composed only by key and random value, without any bits known to the attacker”. Would the fixed bytes of the dom4 function (“SigEd448” and so on) interfere with this? How to work around this?

Or maybe SHAKE256 is already DPA-resistant?

Get this bounty!!!

#StackBounty: #public-key #elliptic-curves #cryptanalysis #signature #dsa Is it safe to reuse a ECDSA nonce for two signatures if the p…

Bounty: 500

We denote the s value of an ECDSA signature $(r, s)$ on a message $m$ as:

Assume two ECDSA signatures sharing the same nonce $(r, s_1) , (r, s_2)$ on two messages $m_1, m_2$, that verify under two pubkeys $x_1G, x_2G$.

If the two public keys are equal then the secret keys should be equal $x_1 = x_2$ and we can easily recover the $k$ using the standard attack on nonce reuse. Once we know $k$ we can recover the secret key.

$frac{H(m_1)-H(m_2)}{(s_1 – s_2)} =frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r – x_2r}$

$x_1 = x_2 rightarrow x_1r – x_2r = 0$

$frac{H(m_1)-H(m_2)}{(s_1 – s_2)} =frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)} = k$

My question is can this attack be made to work if the secret keys are not equal i.e. $x_1 ne x_2$:

$frac{H(m_1)-H(m_2)}{(s_1 – s_2)} =frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r – x_2r} = frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+ (x_1 – x_2)r}$

If you know either $x_1 – x2$ or $frac{x_1}{x_2}$ you should be able to compute $k$ as long as $s_1 ne s_2$.

You can calculate $x_1 – x_2 = frac{H(m_2) – H(m_1)}{r}$ in case where $s_1 – s_2 = 0$. However this case seems to reduce to the hardness of ECDSA since anyone can compute the pubkey for a new message $m_2$ that verifies under first signature $(s, r)$ using public key recovery.

If $s_1 ne s_2$ you can compute $frac{x_1 – x_2}{k}$ which allows you to convert $s_1$ into $s_2$ and vice versa.

Get this bounty!!!

#StackBounty: #elliptic-curves #key-derivation What is this EC key derivation method called?

Bounty: 50

I’m looking to identify the EC key derivation method used in Hyperledger Fabric. I can’t find anything in the docs or the protocol specs, but the functions’ code is here for the private key and the public key.

The derivation function seems to be very simple, DerivedPrivate = MasterPrivate + (k+1) and DerivedPublic = MasterPublic + (k+1) * G all mod N with k being a random derivation data. And yet, I don’t seem to be able to find the name or the source of this method.

I’d like to know about the patent and copyright status of this derivation method, and to do that I need something to google for. I’m also looking for a more formal description of this method.

Get this bounty!!!