75

There are two somewhat orthogonal concepts in backdooring encryption algorithms: The backdoor can be explicit or implicit. An explicit backdoor is one that everybody knows it is there. An implicit backdoor strives at remaining undetected by the algorithm owners. Of course, when there is an explicit backdoor, people tend to avoid the algorithm altogether, so ...


29

I'd say that the whole argument hinges around a "secret attack" that possibly the NSA may know of, enabling them to break some instances of elliptic curves that the rest of the World considers as safe, because the secret attack is, well, secret. This yields to the only possible answer to your question: since secret attacks are secret, they are not known to ...


16

Both of your formulations for encryption backdoors are valid. However, a more efficient way and harder to detect method consist in biaising the random generators used to generate private and public keys (known example). The idea being, if you can predict the random generator output, therefore you can trivially generated the same private/public keys, and then ...


13

Actually, if the RSA key generation is malicious, there are even more subtle ways that can someone can leak the key. The cleverest way I've seen works like this (assuming that we're generating an RSA-1024 key; for RSA-2048, we just use a larger curve): The attacker generates an EC public/private key pair; using a 192 bit curve for RSA-1024 is good. He ...


13

if Ed25519 has gone through rigorous cryptanalysis It is based on Curve25519 which has gone through extensive cryptanalysis. The Ed25519 signature scheme as well is being heavily reviewed and adoption is rapid. There are already a number of papers on the algorithm itself, as well as a few papers on specific implementations. Every part of the algorithm and ...


11

A definition of encryption back doors for those who do not understand encryption. Remember the Battle of Helm's Deep from Lord of the Rings? The big fortress surrounded by a high wall with only one way in? The fortress, the Hornburg, is split into two stages. The Keep is an immensely high structure, accessible from the outside only through a long stone ...


10

can we say that it is fully conforming to the specification, and must have been implemented correctly? No. Is it possible to backdoor a cipher (or hash function, I suppose) in such a way that it still appears to be correct and is compatible with different implementations of the same cipher? Certainly. Say I have an function AES(k,m)=c where variables k ...


10

This has been basically asked already: Should we trust the NIST recommended ECC parameters? History Once it was found that NSA allegedly had inserted backdoor to a cryptographic standard, people started thinking what standard it was. The most common guess is that the Dual EC DRBG is the backdoored standard. However, some amount of (possibly justified) ...


9

Here is a "backdoored" hash function: Let $p = 2q + 1$ be a big prime of length $2048$ bits, such that $q$ is also prime. Let $a$ be an integer of order $q$ modulo $p$, i.e. $a \neq 1$ but $a^q = 1 \pmod p$; it can be shown that $a = 4$ is always a valid solution. Let $s$ be a (secret) integer between $1$ and $q-1$, and let $b = a^s \pmod p$. Then define ...


9

The "exceptional access" thing that law enforcement keeps asking for is best thought of as a master key. You know how in large office buildings, most of the people who work there have keys that only open a few doors, but the janitorial staff and the building management can open all the doors? It would work exactly like that, and it would have exactly the ...


8

My name is Zhenfei Zhang. I work for Security Innovation Inc., which acquired NTRU Inc. in 2010. The R-LWE based key exchange [1] uses a public matrix $a$ which may be manipulated. For instance, if $a$ is an NTRU style public key, i.e., $a = g/f$ where $g$ and $f$ are short, then one can break the system by recovering $f$. In particular, the cited paper ...


7

The field of cryptography that you are looking for is called Kleptography. In kleptography, we are dealing with a setting where the device performing your cryptographic tasks is potentially malicious. Now this device tries to leak information to some attacker that allows this attacker to break the used cryptographic scheme. If I am not mistaken that scheme ...


6

Not quite, but you're close. I will write $[n]A$ for scalar multiplication of the point $A$ on the curve in question by the scalar $n$, as is more typical notation, and I will write $x(A)$ for the least nonnegative integer representative of the $x$ coordinate of $A$. Let $E/k$ be an elliptic curve over the field $k$, and $P$ and $Q$ be two $k$-rational ...


4

RSA modules factoring are not hard in general case. In special cases we can factor numbers easily. One of these special cases is weak prime number, if at least one of two RSA modules primes is weak we can factor it easily. It is interesting that number of such $1024$ bit modules are at least $2^{750}$ and for $2048$ bit is $2^{1500}$. Your mentioned RSA ...


4

There are many things that could be considered as backdoors in encryption algorithms in articles in the media. These don't always agree with the more technical definitions of backdoors, but generally have the result of allowing someone without the password or key to get at the data being protected. For example, in a mobile phone, having a secret PIN code ...


4

The answer is "no", in two ways. First, the implementation of the algorithm could make use of side channels to leak data. The SSL timing attack permits an attacker who can execute multiple encryptions to "tease out" timing information that reveals bits of the key material. The original attack was based on the widely used OpenSSL implementation. Simply ...


4

[Update: See this answer to another question for an example of a back door that can't be detected, but can probably be excluded by demanding a rigid process like RFC 2412 as was used for all the RFC 3526 groups.] If there were a known way to put a back door into Diffie–Hellman parameters, it would be excluded by standard criteria for selecting them. poncho'...


3

Apple are being asked to put a backdoor, not in the encryption algorithms (which are mathematical constructs that you can't add a backdoor to after you've designed it, and tend to be designed to be free of backdoors), but in their encryption system. Cryptography isn't just about the basic algorithms but also how you use them. Other big topics in ...


3

[In the non-prime case] For the backdoor to work, the discrete log should be do-able in $p_i^{k_i-1}(p_i - 1)$ Actually, that's not quite correct, and that's relevant for the answer. If the factorization of $p_i^{k_i-1}(p_i - 1)$ is $p_i^{k_i-1} q_1^a q_2^b ... q_n^z$, then for NOBUS to work, someone else shouldn't be able to find the factors $q_i$. Here'...


3

the general idea is to create an encryption algorithm that can be decrypted 2 different ways. one way (the front door), uses an encryption key (like a password), that the encryptor chooses. the other way (the back door), uses an encryption key that the algorithm designer chooses (or at least knows). you can think of the back door key as a master key that ...


3

Should you pick AES, Twofish, AES(Twofish) or Twofish(AES)? You should pick AES. Also if you should choose Twofish, is it post-quantum computer algorithm proof? There's no current publicly known attack that breaks Twofish any faster than Grover's algorithm (using quantum computers), so it is as secure as AES in that regard. However it is likely much ...


3

On the Practical Exploitability of Dual EC in TLS Implementations by Stephen Checkoway et al. (Usenix 2014) is some research that has been done on how much this NSA backdoor has affected the internet. In short: It's hard to say. What saved a lot of systems from being compriomised is the fact that Dual_EC_DRBG was poorly executed and recommended against early....


3

There are two ways I can see for the RNG to be cooked. (For the record, I don't see any reason at all to suspect this of Intel, but I also think prudent cryptographic design requires us to think through what would happen if our RNG were flawed or backdoored.) First, your RNG could not have enough entropy. That's what got the Netscape RNG many years ago, ...


3

You need to clearly distinguish between the DualEC DRBG algorithm and the elliptic curves over which it is defined. The backdoor in DualEC DRBG needs the attacker to choose P and Q such that they know the scalar $k$ for which $P=kQ$. Pretty much any algorithm which fixes both public keys at the same time without going through private keys is fine. For ...


2

Indeed, in both cases an attacker has to factor the group order and compute logarithms in small subgroups, but in the non-prime case there is an additional step: factoring the modulus. The standard algorithm for computing logarithms in smooth-order groups requires a factorization of the group order. Of course, If those factors are "small", anyone can ...


2

A Cramer-Shoup public key has the form: $B = g_1^{b_1} g_2^{b_2}; \quad C = g_1^{c_1} g_2^{c_2}; \quad D = g_1^{d_1} g_2^{d_2}$ and an encryption of $m$ has the form: $g_1^r, ~ g_2^r, ~ m B^r, ~ (CD^\mu)^r$ where $\mu$ is a hash of the first 3 components. CCA security proof breaks down: In the CCA security proof, you observe that if you know the ...


2

Risks of choosing specific curves Using your own crpytographic scheme (a.k.a. "rolling your own crypto") is extremly bad. Anyone can invent an encryption algorithm they themselves can't break. It's much harder to invent one that no one else can break. It's also bad practice to use a non-open-source API for cryptography because you might not know how exactly ...


2

There are three main kinds of problems that you could conceptually envision in a choice of curve: The curve may have some structure which allows for some known attacks to run efficiently. Possible structural weaknesses include the following (this list is not exhaustive): The chosen curve subgroup may have a non-prime order. The chosen curve subgroup may ...


2

This would be done by a last round attack. The attacker would collect a crib of known pairs of inputs that differ by the plaintext difference (01010001101011 in your example). They would then run through $2^{16}$ guesses for the last round key, for each guess they would be able calculate the difference between each pair in round $r-1$ (by running just one ...


1

I think it'd be more accurate if one says "if IV were chosen arbitrary and / or unknown, then backdoors might be possible". From what I know, the SHA256 IVs are chosing from the fraction parts of well known irrational numbers (though I'm not sure it's sqrt(2) or pi or something else). This way, the only being(s) capable of crafting a backdoor, would be the ...


Only top voted, non community-wiki answers of a minimum length are eligible