News for hackers. Stuff that matters.
Re:Linux Cryptography: Speck's real standing with the academ... by tptacek on Saturday June 02, 2018 @02:05PM (#17215626)
I'm not qualified to challenge Tomer Ashur's analysis of Speck and Simon, and I don't think ISO has any business standardizing those algorithms, so Ashur and I reach the same conclusion about the NSA ciphers.

But I think Ashur is overstating his case.

Ashur repeatedly alludes to the potential for backdoors in Simon and Speck, but never really engages that subject in any detail. That's unsurprising, because the NSA ciphers are both extremely simple, streamlined block cipher designs. There isn't a lot of room in them to insert a "backdoor". Ashur notes that these ciphers were sponsored by the same person that sponsored Dual EC. But Dual EC was self-evidently compatible with backdoors (that was, weirdly, a reason some people --- myself included! I was wrong! --- thought it couldn't be --- the tradecraft was just too clumsy). Dual EC is a PKRNG; embedded in the design is a public key for which we were expected to trust no private key was known. You can't really say that about Speck, or even Simon with its U, V, and W matrices.

Could you deliberately weaken something pretty close to a trivial ARX cipher? I'm sure you could. But NSA doesn't want arbitrary weaknesses; it wants NOBUS backdoors, where it gets cryptographic protection for its own access. It's hard to see how you'd get there with a design as simple as Simon's.

As with previous NSA cipher debates, Ashur takes NSA to task for low security margins. Why so few rounds? Why such simplistic designs? Well, that should be easy to answer: Simon and Speck are "lightweight" ciphers intended for embedded designs. They come with variants with 32-bit block sizes! This also addresses a concern I saw on this HN thread, that NSA was trying to surreptitiously replace AES with a breakable cipher. No, they're not. Even if these had been standardized, you shouldn't be using them; they have a highly specific purpose.

I think the background to this drama is mostly political. I get the sense that NSA has never really complied with the norms of academic cryptography (they're openly derisive of it). Standards groups have, in the past, given some deference to NSA's "alternative norms". That ended with Dual EC, and Simon and Speck are the first post-Dual EC ciphers where NSA is being told they're going to have to follow academic cryptography's norms. Good!

But I'd be careful reaching any conclusions past that.

Corrections welcome!

Re:Linux Cryptography: Speck's real standing with the academ... by pdkl95 on Saturday June 02, 2018 @03:25PM (#17215957)
> But NSA doesn't want arbitrary weaknesses; it wants NOBUS backdoors

The NSA's handling[1] of differential cryptanalysis suggests they could consider an entire analysis technique to be (pseudo-)NOBUS. If they believed they were the only people that knew of a new cryptanalysis technique, I could see them recommending a cypher that is weak to it.

(This is only a hypothetical concern. I have not studied the specifics of Speck/Simon)

[1] Don Coppersmith, in his 1994 paper[2]: "After discussions with NSA, it was decided that disclosure of the design considerations would reveal the technique of differential cryptanalysis, a powerful technique that could be used against many ciphers. This in turn would weaken the competitive advantage the United States enjoyed over other countries in the field of cryptography."

[2] (pdf) http://simson.net/ref/1994/coppersmith94.pdf

Re:Linux Cryptography: Speck's real standing with the academ... by tptacek on Saturday June 02, 2018 @06:29PM (#17216745)
This argument doesn't work. The NSA is pretty universally believed to have optimized the DES s-boxes for resistance to differential cryptanalysis. Obviously, at the time differential was a NOBUS weakness --- NSA would have deployed it against competing cipher designs, which is sort of the whole point of employing cryptanalysts in the first place --- but it was never a NOBUS backdoor in NSA's own design.
Re:Linux Cryptography: Speck's real standing with the academ... by pdkl95 on Saturday June 02, 2018 @07:50PM (#17217068)
> DES ... it was never a NOBUS backdoor in NSA's own design

> Second, you can't argue that something is an NSA backdoor when NSA's only role in standardizing crypto relative to it is to make the standard resistant to it.

I'm not suggesting there was a backdoor in DES; I probably should have made that clearer.

> at the time differential was a NOBUS weakness

Exactly, this is what I'm talking about. This would (hypothetically) incentivise them encourage the use of designs that are vulnerable to the cryptanalysis method that only they know about.

> Dual EC is still a NOBUS backdoor. The "nobody but us" part of it is ensured cryptographically; breaking it likely involves solving the ECDLP

The fundamental problem with that type of NOBUS backdoor is that breaks when someone steals/blackmails/leaks the private key. This should be a concern to any agency that already experienced many of their secrets being exfiltrated by a contractor.

edit:

> (I think people generally used to assume that was true and I think that's less and less so every year)

I generally agree - this seems unlikely in practice, although I don't have good evidence for that belief.

Re:Linux Cryptography: Speck's real standing with the academ... by gdavisson on Sunday June 03, 2018 @03:05AM (#17218326)
It occurs to me that the NSA's behavior in this case is consistent with this being a situation like the DES s-boxes. If they designed Simon & Spec to be resistant to an attack that the open crypto community doesn't know about, they'd be really reluctant to talk about that design process or their internal cryptanalysis of them, for fear of giving away something about their secret attack(s).

So Simon & Spec might be ok. Maybe.

Re:Linux Cryptography: Speck's real standing with the academ... by api on Sunday June 03, 2018 @11:07AM (#17219862)
Wasn't that a past NSA under different leadership? Today's NSA may behave differently.
Re:Linux Cryptography: Speck's real standing with the academ... by tptacek on Sunday June 03, 2018 @11:09AM (#17219881)
It's not my argument that we should trust NSA. We shouldn't. It's that differential cryptanalysis isn't an example of how NSA would backdoor a cipher design, and that the nature of a NOBUS backdoor is more complex than "a weakness only the NSA knows about". Dual EC doesn't have a "weakness" so much as it has a cryptographically secure access mechanism.
Re:Linux Cryptography: Speck's real standing with the academ... by api on Sunday June 03, 2018 @12:16PM (#17220225)
If I were to place a bet I'd bet that Speck in particular is fine. It's so damn simple there is just no place to put a lever. But... it would not be a very large bet. :)
Re:Linux Cryptography: Speck's real standing with the academ... by notveryrational on Saturday June 02, 2018 @07:10PM (#17216919)
I don't think you understood the argument above.

My attempt to clarify it as I understood it:

The argument is that a unique-to-NSA analysis technique could be used to get NOBUS backdoor by virtue that only NSA would be able to use the analysis to get key/message recovery, etc. This is especially true if such a technique were combined with a unique-to-NSA ability to store or process characteristics of a cipher.

The NSA likely has both a unique cryptanalytic techniques and a considerable computational advantage.

The NSA has, before, refused to disclose the motivation for its designs because doing so could leak a unique-to-NSA analysis technique.

The argument (not fact) of the parent comment is that this could be the reason for NSA not disclosing its design rationale now. It could be a backdoor.

The entire purpose of the parent comment is to convey that it is conceivable to NOBUS backdoor simple symmetric ciphers with the resources of the NSA. As such, it is an appropriate response and an argument that _does_ work.

Side note: I remember (different username at the time) discussing with you here, on hacker news, whether DUAL_EC was a backdoor. Of course, that doesn't mean that there is a backdoor in this case.

Re:Linux Cryptography: Speck's real standing with the academ... by tptacek on Saturday June 02, 2018 @07:16PM (#17216946)
I understand the argument fine; it just doesn't cohere.

First, it's self-evident that differential cryptanalysis is not a good example of a NOBUS backdoor, since it was independently discovered multiple times, including by a pair of academics. By contrast, even after BULLRUN, Dual EC is still a NOBUS backdoor. The "nobody but us" part of it is ensured cryptographically; breaking it likely involves solving the ECDLP. It's not "nobody but us until somebody figures it out".

Second, you can't argue that something is an NSA backdoor when NSA's only role in standardizing crypto relative to it is to make the standard resistant to it.

Once again: the NSA may well have many cryptanalytic techniques unknown to the academic literature (I think people generally used to assume that was true and I think that's less and less so every year). But a NOBUS backdoor isn't simply a cipher that NSA can break and nobody else can break yet. It's a cipher that the NSA can break and cannot foresee any adversary breaking within the frontiers of its own knowledge. Whatever cryptanalytic techniques NSA can discover, so too can the Russians, Israelis, French, and Chinese.

The point of a NOBUS backdoor is that it's safe to deploy on your own systems.

Re:Linux Cryptography: Speck's real standing with the academ... by notveryrational on Saturday June 02, 2018 @07:22PM (#17216968)
The NSA is a pragmatic organization and is concerned only by "nobody but us until somebody figures it out", so long as there is an operational advantage it provides to the United States.

We should also note that "nobody but us until somebody figures it out" is true also of ECDLP. I'm not really interested in that argument, because we both know exactly where it goes. Is it different than symmetric cryptography? Yes. But we're talking about symmetric cryptography.

> Second, you can't argue that something is an NSA backdoor when NSA's only role in standardizing crypto relative to it is to make the standard resistant to it.

Nobody is.

Yes, the NSA almost certainly has unique-to-NSA analytic techniques. New techniques are discovered in the academic community on a regular basis - they aren't rare in some way that it would be reasonable to believe that a professional community of the world's best cryptographers with their own cryptanalytic communities, working full time, would have discovered and honed their own. In fact, it would be pretty unusual to believe they don't.

You misunderstand NOBUS. It's purely a pragmatic expression meaning advantage. NSA is under no illusions that their advantage in cryptography on every standard is going to last forever.

Please don't spread FUD on NOBUS.

Re:Linux Cryptography: Speck's real standing with the academ... by tptacek on Saturday June 02, 2018 @07:24PM (#17216974)
I don't understand the distinction you're trying to draw between block ciphers and the ECLDP. Dual EC was an RNG, which is (among other things) an important symmetric primitive. I think the definition of NOBUS that you're working is the one that's broken, not mine.

I also think you're overestimating the frequency with which powerful new techniques for attacking block ciphers occur in the literature. It's 2018 and the debate about Speck's security still hinged in part on Matsui. Fundamental new cryptanalytic techniques against block ciphers are, in fact, pretty rare.

Re:Linux Cryptography: Speck's real standing with the academ... by notveryrational on Saturday June 02, 2018 @07:26PM (#17216981)
> I don't understand the distinction you're trying to draw between block ciphers and the ECLDP. Dual EC was an RNG, which is (among other things) an important symmetric primitive. I think the definition of NOBUS that you're working is the one that's broken, not mine.

I'm not sure where we'll get with it. I'm okay with your misunderstanding.

Please ignore that part of the comment and read the remaining content. Please don't let an objection on a small part of the content distract you from the remaining content of the argument.

> I also think you're overestimating the frequency with which powerful new techniques for attacking block ciphers occur in the literature.

You are clearly underestimating the frequency.

We both understand how heavily caveated your argument referencing Matsui is.

My fear is that your misunderstanding and underestimation will lead to FUD about backdoors, like it did last time with DUAL_EC.

It's also important to note that your argument has shifted significantly in this short exchange.

NSA only cares about NOBUS weaknesses for operational and national security advantages.

Thanks for your time.

Re:Linux Cryptography: Speck's real standing with the academ... by tptacek on Saturday June 02, 2018 @08:48PM (#17217270)
I don't understand what you're trying to say about how "caveated" the Matsui reference is.
Re:Linux Cryptography: Speck's real standing with the academ... by tedunangst on Saturday June 02, 2018 @04:01PM (#17216104)
But didn't they do the exact opposite, and strengthen DES against the attack?
Re:Linux Cryptography: Speck's real standing with the academ... by namibj on Saturday June 02, 2018 @06:15PM (#17216690)
But they did not say why they wanted the S-Boxes changed.
Re:Linux Cryptography: Speck's real standing with the academ... by lvh on Sunday June 03, 2018 @11:53AM (#17220107)
That makes sense even if you assume the NSA is adhering to its mission: if you don't publicly disclose the existence of differential cryptanalysis and the enemy hasn't figured it out the enemy may standardize on a weak cipher. The NSA wins in both of its missions: make the US more secure, make everyone else less secure.
Re:Linux Cryptography: Speck's real standing with the academ... by bo1024 on Saturday June 02, 2018 @03:05PM (#17215868)
- I wonder how the NSA's compute resources translate into an inherent advantage over academics in terms of ability to break these codes. Especially if we are talking about pushing the limits of small margins.

- I don't think it's fair to say the background is "political" if NSA is currently not cooperating with the process. Calling it political makes it sound like their treatment is a function of the broader context or history, but it sounds like they are being treated fairly given how they have acted in this situation.

Re:Linux Cryptography: Speck's real standing with the academ... by tptacek on Saturday June 02, 2018 @06:34PM (#17216769)
It's political because NSA never complied with academic norms, but received deference before the BULLRUN scandal.
Re:Linux Cryptography: Speck's real standing with the academ... by consp on Saturday June 02, 2018 @02:57PM (#17215832)
> Well, that should be easy to answer: Simon and Speck are "lightweight" ciphers intended for embedded designs.

You are providing rationale which the NSA is, according to Ashur, unable to provide in the design documentation/rationale. So I think you are missing the point he's trying to make: If you can't tell me why and are doing hand waving you are either incompetent or deliberately dismissive in which case you should not be trusted.

Re:Linux Cryptography: Speck's real standing with the academ... by dfox on Saturday June 02, 2018 @03:36PM (#17216013)
I think that part of the issue is that people (probably including the WG2) hear NSA and then ignore the lightweight part.

To some extent the lightweightness implies lower standard for the security margins. This is in this case compounded by the fact that WG2 had thrown out most of the truly useful NSA recommended Speck/Simon parameter combinations (things like 32b blocks) even before the current turmoil on the basis that they obviously provide insufficient level of security, which is obviously true for general purpose block cipher, but not for lightweight ("IoT-ish" ;)) applications.

On the other hand I somewhat wonder what motivation exactly NSA had for trying to push these algorithms through ISO.

Re:Linux Cryptography: Speck's real standing with the academ... by tptacek on Saturday June 02, 2018 @06:30PM (#17216753)
No, if you re-read my first sentence, you'll see that I'm not suggesting we should trust NSA.
Re:Linux Cryptography: Speck's real standing with the academ... by cameldrv on Saturday June 02, 2018 @05:40PM (#17216526)
Maybe. NSA wants algorithms to be secure against anyone but them. Perhaps this algorithm cannot contain something in the form of Dual EC_DRBG, where they're effectively handing out a public key as part of the algorithm and they have the private key. However, it could also be that there are particulars of the algorithm that make hardware that the NSA has and doesn't expect anyone else to be able to obtain, work especially well.
Re:Linux Cryptography: Speck's real standing with the academ... by tptacek on Saturday June 02, 2018 @06:33PM (#17216763)
For us, "IOT" means "Internet-connected refrigerator". From NSA's vantage point, though, it includes billions of dollars in embedded industrial equipment that is taking advantage of the same technology that's allowing us to wire up our toasters. If that equipment is insecure simply because vendors can't get AES working on a PIC or MSP embedded SOC, you have a nation-scale problem. It then starts to make sense that they'd work to provide an "officially blessed" cipher that can work in those environments.

We also forget that though we don't trust NSA (and shouldn't), American industry sure does.