0
$\begingroup$

I am working on a very resource-constrained environment. Using a standard peer reviewed library isn't possible because it won't fit within the RAM requirements of the device (~5K unused ram without crypto). The library I've modified is called microecdsa, and the way it chooses k is as follows. 

for (;;) {
        // generate random number k
        for (i = 0; i < 8; i++) {
            k.val[i] = random32() & 0x3FFFFFFF;
        }
        k.val[8] = random32() & 0xFFFF;
        // if k is too big or too small, we don't like it
        if (k.val[5] == 0x3FFFFFFF && k.val[6] == 0x3FFFFFFF && k.val[7] == 0x3FFFFFFF && k.val[8] == 0xFFFF) continue;
        if (k.val[5] == 0x0 && k.val[6] == 0x0 && k.val[7] == 0x0 && k.val[8] == 0x0) continue;
        // compute k*G
        scalar_multiply(&k, &R);
        // r = (rx mod n)
        mod(&R.x, &order256k1);
        // if r is zero, we try different k
        for (i = 0; i < 9; i++) {
            if (R.x.val[i] != 0) break;
        }
        if (i == 9) continue;
        inverse(&k, &order256k1);
        temp = 0;
        for (i = 0; i < 8; i++) {
            temp += (((uint64_t)read_be(priv_key + (7 - i) * 4)) << (2 * i));
            da->val[i] = temp & 0x3FFFFFFF;
            temp >>= 30;
        }
        da->val[8] = temp;
        multiply(&R.x, da, &order256k1);
        for (i = 0; i < 8; i++) {
            da->val[i] += z.val[i];
            da->val[i+1] += (da->val[i] >> 30);
            da->val[i] &= 0x3FFFFFFF;
        }
        da->val[8] += z.val[8];
        multiply(da, &k, &order256k1);
        mod(&k, &order256k1);
        for (i = 0; i < 9; i++) {
            if (k.val[i] != 0) break;
        }
        if (i == 9) continue;
        // we are done, R.x and k is the result signature
        break;
}

The issue is, using this code above I can only generate legitimate signatures occationally. If I modify the first few lines to be the following the signatures always validate. Leaving the code unmodified leads to the signatures being invalid semi-regularly. 

// generate random number k
for (i = 0; i < 8; i++) {
        k.val[i] = 1;
        if(i>0 && i <8){
            k.val[i] = random32() & 0x3FFFFFFF;
        }
}
k.val[8] = 1;

Is this a safe modification? Meaning that the I've only eliminated 48 bits of entropy and we still have 224 bits of entropy, or am I misguided. If an attacker knows the first four bytes and the last two bytes of k, can they compromise the security of the key.

Also as a side note if you know of any safe and low resources ecdsa secp256k1 implementation please let me know.

Thank you.

| improve this question | |
$\endgroup$
  • 3
    $\begingroup$ If you have access to a hash function already, can't you make for a deterministic derivation of k from secret key + message? It's what Bitcoin Core does. You ABSOLUTELY DO NOT want k to have predictable patterns $\endgroup$ – Natanael Apr 9 '19 at 0:41
  • $\begingroup$ Does random32() return cryptographically secure random numbers? $\endgroup$ – forest Apr 9 '19 at 0:48
  • 3
    $\begingroup$ This is almost certainly not a safe modification. The goal here is to sample from the uniform distribution on scalars—any substantial nonuniformity may leak the private key. It's not immediately clear to me why the original code clears many of the bits in $k$, nor exactly what it's rejecting: usually the approach is to sample 256-bit integers $k$ and reject $k \geq n$. Another approach is to sample a single 512-bit integer $k$ and reduce modulo $n$—or derive a 512-bit $k$ as a pseudorandom function of the message and reduce modulo $n$, like Ed25519 does. $\endgroup$ – Squeamish Ossifrage Apr 9 '19 at 1:49
  • $\begingroup$ Thanks guys I won't use this method if it's not safe, and it doesn't seem like it is :p $\endgroup$ – NateBrune Apr 9 '19 at 2:46
  • 1
    $\begingroup$ Actually the situation is more dramatic than Squeamish portraied: Even if you pick random 256-bit values and reduce them $\bmod q$, then $2^{256}-q$ $k$-values will have probability $2^{-255}$ of being picked and the remaing $2q-2^{256}$ values will have probability $2^{-256}$ of being picked. Even this seemingly miniscule nonuniformity is already exploitable. $\endgroup$ – SEJPM♦ Apr 9 '19 at 16:45

Your Answer

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

Browse other questions tagged or ask your own question.