Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
samvartaka.github.io
Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
1–10 of 13 posts
Re: Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
#2If anyone's particularly bored, the password, from which the master key used in my original backdoor is derived, should be fairly easy to crack. It is eight nonrandom characters.
Re: Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
#3It seems trivial to avoid detection: Just generate a random number, and if it's a valid x-coordinate, only then backdoor it. Sure, you'll only backdoor half the keys, but then you have to weigh whether the probability of being detected and severity of it is worth the cost.
Re: Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
#4Of course, the Elligator and related mappings allow for (a subset of) valid curve points to be mapped to indistinguishable bit strings, which is very handy in some protocols. A backdoor merchant using Elligator 2, or Elligator Squared, in this particular setup wouldn't be detectable.
Re: Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
#5Of course, the Elligator and related mappings allow for (a subset of) valid curve points to be mapped to indistinguishable bit strings, which is very handy in some protocols. A backdoor merchant using Elligator 2, or Elligator Squared, in this particular setup wouldn't be detectable.
I don't think you even need anything that fancy - pretty sure just encrypting the leak again with a fixed AES key would do the job well enough. If someone manages to get hold of the AES key they could use it distinguish backdoored keys from random, but at that point you've been caught anyway.
Re: Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
#6Of course, the Elligator and related mappings allow for (a subset of) valid curve points to be mapped to indistinguishable bit strings, which is very handy in some protocols. A backdoor merchant using Elligator 2, or Elligator Squared, in this particular setup wouldn't be detectable.
Exactly. I attack and repair the Curve25519 backdoor using Elligator in illusoryTLS, a talk delivered at HITB SecConf (and other conferences) based on my entry to the first Underhanded Crypto Contest http://illusoryTLS.com/
Re: Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
#7Of course, the Elligator and related mappings allow for (a subset of) valid curve points to be mapped to indistinguishable bit strings, which is very handy in some protocols. A backdoor merchant using Elligator 2, or Elligator Squared, in this particular setup wouldn't be detectable.
I don't think you even need anything that fancy - pretty sure just encrypting the leak again with a fixed AES key would do the job well enough. If someone manages to get hold of the AES key they could use it distinguish backdoored keys from random, but at that point you've been caught anyway.
There are a number of properties that a carefully designed asymmetric backdoor is expected to have. NOBUS (Nobody But Us) and forward-secrecy are among them. With a forward-secret backdoor, if a reverse-engineer breaches the key-generator, then the previously stolen information remains confidential.
If the key-generator embeds a secret key (for seed exfiltration), the backdoor design will never be robust against reverse engineering. In fact, exposure of the embedded key gives to the attacker the ability to retroactively factor with ease the moduli of public-keys generated in the past, and recover the private-keys.
The designs of Curve25519 and illusoryTLS embed only an elliptic-curve public-key. Therefore, the exploitation requires access to the associated private-key /i.e., NOBUS property).
For the longer story about the sorrow state of the Web PKI and the nitty gritty details on this cryptographic backdoor, you may want to review the illusoryTLS whitepaper http://conference.hitb.org/hitbsecconf2015ams/wp-content/upl...
Re: Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
#8If anyone's particularly bored, the password, from which the master key used in my original backdoor is derived, should be fairly easy to crack. It is eight nonrandom characters.
Actually, you don't need the master password to recover. Reusing master hash (MASTER_PUB_HEX) works just fine.
https://gist.github.com/aexaey/3646bb438f8712cbadf5/revision...
Scroll to the third change from the top - stupid github doesn't allow (an obvious) way to make a direct link to a particular gist's revision.
Re: Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
#9You should cut your losses. You are digging a deeper hole as an enemy of God.
Re: Detecting an asymmetric Curve25519 backdoor in RSA key generation algorithms
#10If anyone's particularly bored, the password, from which the master key used in my original backdoor is derived, should be fairly easy to crack. It is eight nonrandom characters.
Actually, you don't need the master password to recover. Reusing master hash (MASTER_PUB_HEX) works just fine. https://gist.github.com/aexaey/3646bb438f8712cbadf5/revision... Scroll to the third change from the top - stupid github doesn't allow (an obvious) way to make a direct link to a particular gist's revision.
That only works in your changed version because it incorrectly uses MASTER_PUB_HEX as a private key.