Hello, I have this python code i want to replicate in nim
def bytes_to_clamped_scalar(s):
# Ed25519 private keys clamp the scalar to ensure two things:
# 1: integer value is in L/2 .. L, to avoid small-logarithm
# non-wraparaound
# 2: low-order 3 bits are zero, so a small-subgroup attack won't learn
# any information
# set the top two bits to 01, and the bottom three to 000
a_unclamped = bytes_to_scalar(s)
AND_CLAMP = (1<<254) - 1 - 7
OR_CLAMP = (1<<254)
a_clamped = (a_unclamped & AND_CLAMP) | OR_CLAMP
return a_clamped
So I did a bit more research and found that python implements integers in a way that allows it to accommodate a large range of integers at the cost of performance.
Now to the question part, this code replication is part of my attempt to replicate the pure python code in the project pured25519. The portion of code I want to replicate is the code that allows the generation of public key from 32 bytes seed located at public key function. Is there a way I can implement this in pure nim without having to resort to some wizardry?
Consider also constantine, which was especially designed for crypto applications . BigInt type and shift procs available is this module specifically: https://github.com/mratsim/constantine/blob/1c5341fd7e8af9084223b5bce616b4a8262eab14/constantine/math/arithmetic/bigints.nim
Should be available if you import constantine/math/arithmetic.
Obligatory disclaimer:
Don't use your code in production, the scalar you are processing is a cryptographic private key and issues in your code may expose you to identity theft, losing money (by someone pretending to be you), remote SSH access and what not.
It's fine for learning purpose though.
For example, using any library that dynamically allocate bigint as a backend would expose you to the same CVE as Keepass https://www.helpnetsecurity.com/2023/05/17/cve-2023-32784/ by triggering a RAM memory dump or swap when hibernating.
Anyway, you need to implement big integers or use a (cryptographic) big integer library.
The OR_CLAMP is to ensure the high bit is set The AND_CLAMP is to ensure the last 3 bits are unset to avoid being victim of Monero attack:
The scalar is clamped. Bit 255 is cleared and bit 254 is set to prevent timing leaks in poor implementations, and put a lower bound on standard attacks. More importantly, bits 0, 1, and 2 are cleared, to make sure the scalar is a multiple of 8. This guarantees that the low order component of the point, if any, will be absorbed by the scalar multiplication, such that the resulting point will be on the prime-order subgroup.
The second trick is especially important: it guarantees that the scalar multiplication between your secret key and an attacker controlled point on the curve can only yield two kinds of results:
A point on the curve, that has prime order. The attacker don't learn anything about your private key (at least not without solving discrete logarithm first), and they can't control which point on the curve you are computing. We're good.
Zero. Okay, the attacker did manage to force this output, but this only (and always) happens when they gave you a low order point. So again, they learned nothing about your private key. And if you needed to check for low order output (some protocols, like CPace, require this check), you only need to make sure it's not zero (use a constant-time comparison, please).
This is what is done in these lines: https://github.com/status-im/nim-libp2p/blob/225accd/libp2p/crypto/ed25519/ed25519.nim#L1664-L1666 (note that the representation used for Curve25519 here is from the reference implementation, codenamed ref10 from https://ed25519.cr.yp.to/software.html. It's not simple bigints.)
If you want to play with a BigInt backend you can use Constantine, with the bigint part: https://github.com/mratsim/constantine/blob/master/constantine/math/arithmetic/bigints.nim
import
../constantine/math/arithmetic/bigints,
../constantine/math/io/io_bigints,
../constantine/platforms/abstractions
func bytes_to_clamped_scalar(dst: var BigInt[255], src: array[32, byte]) =
let ok = dst.unmarshal(src, srcEndianness = bigEndian)
doAssert ok
# TODO: your Python may be incorrect if bytes_to_scalar doesn't ignore bit 255
# The code here doesn't ignore bit 255 but it should be 0 or deserialization fails
# Set the 3 low bits to 0 (i.e. -8)
dst.limbs[0] = dst.limbs[0] and cast[SecretWord](-8)
# Set the high bit
dst.setBit(254)
't use your code in production, the scalar you are processing is a cryptographic private key and issues in your code may expose you to identity theft, losing money (by someone pretending to be you), remote SSH access and what not.I am not very experienced in cryptography. But, to put into context what I am trying to do is to generate public key and private key for aptos wallets from the 32 bytes seed keys given after creating the wallet.
I already tried stealing code from libp2p to achieve this but the public key and private key generated are different all the time. I assume this is what you mean by the attacker not being able to get the private key. But any time I tried with the official aptos python sdk the same seed always yields the same value, there is no randomly generated value as with my contraption with libp2p code.
Now the question is, is it also a security flaw that the official python sdk generates the same public key and private key (did not check the private key but i assume it's the same since the public key is also the same) from the seed?
I already tried stealing code from libp2p to achieve this but the public key and private key generated are different all the time. I assume this is what you mean by the attacker not being able to get the private key. But any time I tried with the official aptos python sdk the same seed always yields the same value, there is no randomly generated value as with my contraption with libp2p code.
I'm not sure what you tried, if you initialize with the same 32 bytes you get the same value. So if you don't there is a bug, either you're echoing an uninitialized buffer, or you were reading the private key from an uninitialized buffer (buffer overflow?).
Also Aptos seems to be using NaCl: https://github.com/aptos-labs/aptos-core/blob/wallet-v1.0.0/ecosystem/python/sdk/aptos_sdk/ed25519.py#L8
So use libsodium: https://github.com/FedericoCeratto/nim-libsodium
If you go further in wallet dev, be aware on how to do key derivation from a mnemonic using BIP44, see Aptos specs: https://github.com/aptos-labs/aptos-core/blob/9fa0102/developer-docs-site/docs/standards/wallets.md?plain=1#L2
Implementing elliptic curve from scratch with no background in cryptography engineering is a tall order.
For production (and not as a learning experience), it's probably easier to debug why libp2p implementation gives you a different key everytime. It has been audited and is straight from a reference implementation (and still had issues).
There are many many things to be aware of to implement cryptography for production use, see audit:
And then the testing and fuzzing suite needs to be extensive.
Regarding libsodium, I'm sure there is a libsodium-js package and if not, probably there is a way to compile it to WASM?