I think e needs to be coprime with phi(N) rather than N itself. This is so you can find d = e^-1 mod phi(N), which would otherwise not exist.
Of course, if e shares a factor with N, you have bigger problems.
1,326 karma · joined July 6, 2009
Of course, if e shares a factor with N, you have bigger problems.
You're correct that the ring of integers mod n with n composite will have small multiplicative subgroups. But so will the integers mod p with p prime. At the very least, 1 and p-1 will always have orders 1 and 2, respectively. I could be wrong, but I don't think the primality or compositeness of the modulus alone tells you much about the smoothness of the group order.
Small subgroups may not always lead to key recovery, but they can lead to key dictation in certain protocols. So subgroup-confinement attacks are always a consideration in this setting.
If you want to learn more about subgroup-confinement attacks on DH and ECDH, check out set 8 of cryptopals. Mail set8.cryptopals@gmail.com with subject "Crazy Flamboyant for the Rap Enjoyment".
There are also a few videos where a guy does some live ROM-hacking on the original Zelda.
The NIST document specifying Dual EC offers default values for each curve. P is the usual base point for the curve; an arbitrary point Q is provided without justification or details of its generation.
Because the NIST curves have cofactor 1, all points other than the identity generate the same subgroup. This means any two points P and Q are related by some scalar d such that d * P = Q. Knowledge of d is the back door in the generator.
This also implies a simple means for choosing Q given P: pick a random integer d and calculate Q = d * P. Publish P and Q and then write down d someplace safe. This is exactly how NSA is speculated to have chosen the Dual EC parameters.
However, the NIST document also specifies a method for generating alternative points. It boils down to hashing a random seed and mapping the result to a curve point. If you generate the base points P and Q like this, the relationship between them is unknown. The scalar d still exists, but now no one knows what it is. Without that knowledge, there is no back door.
It's not clear from that page how Juniper chose the parameters. Maybe they did choose a random scalar and multiply P, or maybe they followed the standard. The information on that page isn't enough to say one way or the other.
EDIT: Just to be clear, I'm not saying this isn't something to worry about. You should distrust and avoid anything that relies on Dual EC. I'm only saying there is not enough information to say definitively that Juniper put a back door in their own product, intentionally or otherwise.
Public-key schemes based on factoring and discrete logarithms are undone by Shor's algorithm (https://en.wikipedia.org/wiki/Shor%27s_algorithm), but there are asymmetric systems not known to be vulnerable to quantum algorithms. They are less mature, but researchers are working it.
There's some good high-level information at http://pqcrypto.org/ and in this paper: http://pqcrypto.eu/docs/initial-recommendations.pdf.
This set provides an introduction to practical attacks on elliptic curves as well as some neat key-recovery attacks on GCM.
I agree, POODLE is a close analog.
Lucky13 and POODLE are the chosen-ciphertext attacks.
EDIT: Some more details:
BEAST takes advantage of predictable IVs in SSLv3 and TLS 1.0. In these protocols, the IV for each new record is simply the last block of the previous record. An attacker monitoring traffic on the wire can use this predictability to build an encryption oracle and guess-and-check the contents of ciphertext blocks.
CRIME uses plaintext compression to its advantage. A message with longer common substrings will compress slightly better than one without, and this is reflected in the ciphertext length. An attacker can make adaptively chosen guesses at substrings included in the message to recover, e.g., session cookies.
For example, check out https://www.openssl.org/~bodo/tls-cbc.txt. This is a document published by Bodo Moeller in the early 2000s that details multiple theoretical weaknesses in the CBC mode used in TLS. Read it top to bottom and see how many practical attacks on TLS you can count.
Argh. No.
> Should you use it? No. There's many important missing features that are present in proper symmetric encryption tools, such as proper key derivation, protection against modification, IVs, and fewer bugs.
This (buried) warning makes these things sound like bells and whistles. The truth is they're essential to security.
Here are some good reasons not to use this for anything:
1. It conflates passwords with keys. Users will not choose high-entropy passwords when left to their own devices.
2. It doesn't take an IV. This means a given password will always generate the same key stream, which means password reuse will lead to plaintext recovery by simple statistical methods. There are no warnings about this.
3. It's not authenticated. An attacker can modify messages in flight with unexpected consequences that very often include plaintext recovery.
4. RC4 is irreparably broken. Dropping 1024 bytes from the key stream might help in the author's intended use-case (assuming users adhere to it), but this is not an effective mitigation in general. The best attacks on RC4 rely on periodic biases that persist over the entire key stream.
What would it mean for a curve to have a "kleptographic" back door? Only one base point P is defined in the curve parameters, so there is no hidden relationship to take advantage of. It is possible there are weaknesses in the NIST curves, but if so:
1. They must lie in the curve parameters themselves, i.e. something anyone could conceivably discover.
2. They must rely on a significant advance in ECDLP, e.g. a new class of weak curve.
I think the paper is maybe slightly dismissive, closer to neutral: "it is conceivable the NSA has found ...".
The post seems more enthusiastic:
"the most intriguing hypotheses in the paper"
"Beginning with the smallest of the standard curves, P-256, which would now provide less than the required 128-bit security.
Did I mention that as part of the recent announcement, NSA also deprecated P-256?"
He backtracks a little in the following paragraph ("Of course, there’s no reason to believe ..."), but I think the conspiratorial tone is pretty well established by then.
It's also just the fact that he spends about a third of the post talking about this explanation without really covering any of the others. If I hadn't read the paper, I'd come away with the impression that this is the main theory they put forth.
> However, it will require major advances in physics and engineering before quantum computing can scale significantly. When that happens, of course P-256 and P-384 will fall first. But, as the head of cybersecurity research at a major corporation put it, “after that it’s just a matter of money” before RSA-3072 is broken. At the point when P-384 is broken it would be unwise to use either ECC or RSA. It is not likely that the gap between quantum cryptanalysis of a 384-bit key and a 3072-bit key will be great enough to serve as a basis for a cryptographic strategy.
I definitely do not think the proliferation of unvetted, anonymous crypto libraries is a good thing. How many people have the expertise to write this kind of thing? How many have the expertise to evaluate its quality?
For example, the documentation for the linked library says: "we've also added integrity checking in the form of a SHA 256 hash." This is a huge red flag: hashes provide integrity, but not authenticity, which is really what you want here. But then you go and look at the source code and find that they are actually using HMAC-SHA256, which does provide authenticity. So the documentation is not an accurate description of what's going on, and you need to go and look at the source to find out that it really is okay (in this particular aspect, though it doesn't inspire confidence for the future).
My point is not to say that this particular library is terrible or anything. Just that we have limited resources, and we're better off consolidating to a very small number of solutions designed, written, and validated by experts.
I have no idea if that is what this specific dig ("they already master the art of snake oil") pertains to.
GCM is also difficult to implement in software for the same reasons AES is: the high-performance implementation strategies tend to rely on precomputed tables. This puts memory pressure on servers that handle a large number of keys concurrently. Table-based implementations also tend to expose cache-timing side channels. Fortunately, modern Intel machines have instructions (e.g. PCLMULQDQ) that aid implementations, though I'm not sure how widespread their use is in practice.
To be very clear, GCM is still a fine choice, and much safer than composing authentication and encryption yourself.
If you have access to it, NaCl's Secret Box is a good choice that avoids these problems. Libsodium implements NaCl and is pretty widely available, I think. OCB is also a good choice, though I haven't seen many implementations of this.
EDIT: For those interested, Niels Ferguson's criticism of GCM (http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comment...) is a great read. Lots of minor practical issues (e.g. specifying bit strings rather than byte strings, performance measurement across platforms, etc.) along with the aforementioned attack on short authentication tags.
This should be "96 bits".
I'm not sure this is a major vulnerability in practice, but it is strange not even to mention 10+ years of cache-timing attacks against AES.