People have had that reaction to NSA-endorsed cryptosystems ever since they withheld the derivation of the DES S-boxes for a number of years. Wikipedia states [1]:
"The 8 S-Boxes of DES were the subject of intense study for many years out of a concern that a backdoor -- a vulnerability known only to its designers -- might have been planted in the cipher. The S-Box design criteria were eventually published (in Coppersmith 1994) after the public rediscovery of differential cryptanalysis, showing that they had been carefully tuned to increase resistance against this specific attack."
Ha, more likely a recruiting tool! Reads ArticleChecks Email "Hello! We are looking for programmers with an understanding of the SIMON and SPECK families of lightweight block ciphers."
Well that's a particular type of trap. To be honest, I wouldn't want to be a programmer or sysadmin at the NSA right now. They're going to "punish" all the remaining employees because of Snowden's actions.
I think most of them have been independently tested and vetted as well, and I would expect that the crypto community [read: people smarter than me] will do the same for SIMON and SPECK
TEA is another lightweight cipher. AES isn't lightweight. At the end of the first 1/3rd of this paper there's a chart comparing code size and throughput for ciphers by key/block size; that's what you want to pay attention to.
You would tend to use ciphers like these in applications where the time/value of your information wouldn't justify the silicon or code space of a general-purpose cipher. Note also that neither of these ciphers were designed with any thought to the open-key security model, where the adversary knows the key in advance, as is the case with hashes. I don't know what this means to to the security of using, say, SIMON in a construction where the cipher core is also a PRF for a MAC, like CCM.
I'm confused about the latter half of your comment. CCM is basically CTR mode plus CBC-MAC; certainly the adversary isn't meant to have the key to your MAC? (Your comment about open-key use does make sense; it's just that I'm not sure it applies to CCM.)
Also, I'll channel your for a moment: don't build your own crypto! And don't use lightweight block ciphers for data you care about: many are designed to skirt the edges of "too weak", their implementations haven't been side-channel-attacked quite as often as OpenSSL's AES, and they haven't been reviewed to anything like the extent that AES has been and/or have been found wanting (TEA). Yes, experts can put them to good use, but be very careful and don't use them before ruling out the conservative AES-HMAC-SHA2 as well as more modern constructions like Keccak in AEAD mode.
They're a dime a dozen these days. Incomplete list, block ciphers only: HIGHT [1], PRESENT [2], KLEIN [3], PRINTcipher [4], KATAN [5], TWINE [6], LED [7], PRINCE [8], Piccolo [9].
AES is generally known to be doable in around 2500 gates, or gate-equivalents. These lightweight ciphers aim lower, towards the 1000 or so.
The design looks very elegant, and they manage to avoid using sboxes at all, departing from most known lightweight ciphers. It also has decent performance in 64-bit hardware, without having to recur to bitslicing, which is nice.
The whole round has algebraic degree 2, like Keccak, which makes things easier to analyze when it comes to differential and linear cryptanalysis. Hard to say much more at this point.
This is very naive. The NSA is a $10bn/year agency that functions as our nation's center of excellence for breaking into computers. They don't need to sabotage PDFs to pop your machine.
I was thinking more along the lines of government waste and inefficiency, having some crappy document management system that can only serve PDF's, even for 404's.
No, but they need to ask HW mfrs like Cisco to put backdoors in for NSA's use... at least, that's what some Chinese newspaper was suggesting recently. Based on the talks I've been watching by the group of NSA whistleblowers who worked on what became PRISM, I'm not sure NSA was a "center of excellence" regarding computer networks back in the 90's, when the general public started connecting to the internet. There was (and maybe still is) a huge effort to "transform" the agency. Away from what? Just my opinion, but it seems they are spending a lot of money and effort to become a center of excellence. It's like an updated version of that old Uncle Sam poster: "We want you," addressed at BlackHat attendees.
May I ask what convinced you they were a center of excellence in the 90's? I ask this sincerely, not in rebuttal.
What do you make of the comments of Binney that NSA was caught sleeping (for lack of a better phrase) by 9/11? Why the need to "transform" the agency? He said he headed a group that was responsible for instituting change in the organization. I believe they even had "change" in the name given to the group. It sure seems like they want(ed) to morph into something they were not previously.
I interviewed with them in the late 80's. they were just then moving away from their own proprietary programming language(s?), not ADA, just beginning to open into C, perhaps others. Anyone know of this? What is the name of this language? Interesting NSA history transition, presumably, from the considerable force of recruiting mass civilian literacy with the downside of its security vulnerability.
It's worth mentioning that NSA is a very large organization with lots of different functions. I can imagine a stodgy Ada-programming division in the NSA living alongside a division that, say, knew how to reliably exploit heap overflows in 1991.
Recent events raised never ending question of "could the government place a backdoor in DES/AES/SHA/etc.?"
My personal perception (based on available evidence) is that government crypto is as strong as possible, but is weakened where needed via policies. A decade ago during crypto export limitation, there were no backdoors, but a policy: you may export only keys that long [so we can bruteforce them cheaper].
Another example: SSL is technically secure, but its biggest weakness is trust in a limited list of certificate authorities (CAs) like VeriSign. Then, there is policy that certificate authorities should give up their private keys when FBI/CIA asks for them.
Another example: you may encrypt your files, but must give away your password to a court.
Also, it makes sense economically. Government people need strong crypto like everyone else and the best way to test and verify it is by opening it up and deploying as widely as possible. So mistakes are noticed sooner than later. Then, people with guns will make sure you give up your secrets when they need you to.
I believe crypto systems are alright. It is policies and violent coercion we should be afraid of.
However it seems to me that to this day there is no proof they intentionally tried to weaken a standardized crypto algorithm, they seem to have instead relied in the past on imposing reduced sizes of keys. But even that seems to have changed nowadays, AES 256 bits despite all the scrutiny seems to still be a safe choice. Of course, I don't know what are their plans concerning crypto but the backlash will be huge if it appeared they rigged an algorithm. Of course, if they happened to honestly find a significant flaw or make a breakthrough in quantum computing for instance I doubt they would tell the public either.
Having a CAs private keys allows for crude impersonation, not wholesale interception as many believe. (State actors have gone this route in the past and been quickly discovered)
Google.com generates a public/private key pair and has the public key signed by a CA. The signature only says "I verify this public key really belongs to google.com," it does not become part of the actual cryptographic transaction.
Recent Q/A session with Edward Snowden [1] supports your assumption.
Q: Is encrypting my email any good at defeating the NSA survelielance? Id my data protected by standard encryption?
A: Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it.
> Government people need strong crypto like everyone else and the best way to test and verify it is by opening it up and deploying as widely as possible.
One counter example: Clifford Cocks created a public key crypto system before RSA did, and GCHQ kept it secret for many years.
is it unusual to use "bitwise and" inside the feistel function? i thought that normally xor or modular addition or shifts or permutations (nx1 s-boxes) were used, which keep all the information (in some sense). "bitwise and" isn't like that (i don't have the right word for this distinction, sorry. maybe "invertible" is the word?) but is used here. anyone know why? or is this a distinction i've invented that has no basis in fact?
obviously it doesn't matter (decryption still works) as long as it's inside the feistel function itself. so i guess maybe i am just muddling that with how things must be outside that?
Apropos nothing (because I noticed this when looking for another cipher with AND in its round function): to appreciate how simple the design of SIMON (or SPECK) is, read the first (or second) half of the NSA paper... then read the Kelsey and Schneier's Twofish paper.
There are 2 separate aspects here: AND (the instruction itself) and invertibility.
Indirectly, every decent round function ever created has had AND. At the bit level, you can't have a nonlinear function without AND. The carry bit in additions, for example, is given by a_i&b_i ^ a_i&cin ^ b_i&cin. Using AND directly, though, is pretty rare though not unheard of, since as CPU instructions go AND is doing relatively little work compared to more powerful instructions such as ADD, SUB, MUL, or table lookups. You see AND, though not bitwise, a lot more in hardware-friendly designs that employ NLFSRs as primitives.
As for invertibility, in Feistel ciphers it is not really a requirement, as you point out, f only really needs to be a PRF. That being said, I have heard the argument that making f invertible does preserve information before; I do not know where this argument comes from, and as far as I know it's not formalized anywhere. DES and Blowfish are Feistel ciphers without invertible f, and don't have that bad of a security record.
i was just thinking about this in the shower and came up with this handwaving justification:
if you have two random values, using AND biases the number of set bits on average (you get 3/4 zeroes in the output). in other words, it lowers the (shannon) entropy in the circuit, on average, while an invertible function preserves entropy (it has to, right?).
entropy sounds like a smart thing to preserve in a PRF so this would seem like an argument for invertibility.
BUT it's only preserving entropy on average, and what you really care about is the entropy in the difference between input and ouptut in any single round. which is not the same thing at all (identity function is great for the former, not so good for the latter). so you could imagine there's some trade-off...
forgive me if this makes no sense. it just seemed interesting when i thought of it :o)
For a more accessible introduction to SIMON and SPECK take a look at this IETF mailing list message[1] especially the video with introduction by the NSA developers:
"Today at the MIT Media Lab Legal Hack-a-thon on Identity we had a great
presentation from a couple of designers from the NSA regarding their new
lightweight ciphers called SIMON and SPECK. These ciphers are designed
for low-power limited gate devices (such as RFID and similar devices).
Note: I changed the youtube video from a tinyurl link to the actual link. If you want to tell tinyurl that you visited the youtube video click here: http://tinyurl.com/bf6fbju
46 comments
[ 3.3 ms ] story [ 100 ms ] thread"The 8 S-Boxes of DES were the subject of intense study for many years out of a concern that a backdoor -- a vulnerability known only to its designers -- might have been planted in the cipher. The S-Box design criteria were eventually published (in Coppersmith 1994) after the public rediscovery of differential cryptanalysis, showing that they had been carefully tuned to increase resistance against this specific attack."
[1] http://en.wikipedia.org/wiki/Substitution_box
It's healthy to suspect crypto systems because of their role in protecting us.
(DES, AES, SHA1, etc)
You would tend to use ciphers like these in applications where the time/value of your information wouldn't justify the silicon or code space of a general-purpose cipher. Note also that neither of these ciphers were designed with any thought to the open-key security model, where the adversary knows the key in advance, as is the case with hashes. I don't know what this means to to the security of using, say, SIMON in a construction where the cipher core is also a PRF for a MAC, like CCM.
Also, I'll channel your for a moment: don't build your own crypto! And don't use lightweight block ciphers for data you care about: many are designed to skirt the edges of "too weak", their implementations haven't been side-channel-attacked quite as often as OpenSSL's AES, and they haven't been reviewed to anything like the extent that AES has been and/or have been found wanting (TEA). Yes, experts can put them to good use, but be very careful and don't use them before ruling out the conservative AES-HMAC-SHA2 as well as more modern constructions like Keccak in AEAD mode.
I think the Xbox TEA hash is another example of a lightweight cipher having problems when used as a hash construction.
Certainly I wouldn't ever advise someone to use SIMON or SPECK in production.
AES is generally known to be doable in around 2500 gates, or gate-equivalents. These lightweight ciphers aim lower, towards the 1000 or so.
[1] http://www.iacr.org/cryptodb/archive/2006/CHES/04/04.pdf
[2] http://homes.esat.kuleuven.be/~abogdano/papers/present_ches0...
[3] http://doc.utwente.nl/73129/1/The_KLEIN_Block_Cipher.pdf
[4] http://www.iacr.org/archive/ches2010/62250016/62250016.pdf
[5] http://www.cs.technion.ac.il/~orrd/KATAN/CHES2009.pdf
[6] http://www.nec.co.jp/rd/media/code/research/images/twine_LC1...
[7] http://eprint.iacr.org/2012/600.pdf
[8] http://eprint.iacr.org/2012/529.pdf
[9] http://link.springer.com/chapter/10.1007%2F978-3-642-23951-9...
The whole round has algebraic degree 2, like Keccak, which makes things easier to analyze when it comes to differential and linear cryptanalysis. Hard to say much more at this point.
https://www.youtube.com/watch?v=vtyo4nWGBwk
"Gordon Adams, a former White House budget official for national security, said he wouldn't be surprised if NSA's resources are "well north" of $20 billion a year." http://money.cnn.com/2013/06/07/news/economy/nsa-surveillanc...
You are incorrect in speculating that they're just now becoming one.
What do you make of the comments of Binney that NSA was caught sleeping (for lack of a better phrase) by 9/11? Why the need to "transform" the agency? He said he headed a group that was responsible for instituting change in the organization. I believe they even had "change" in the name given to the group. It sure seems like they want(ed) to morph into something they were not previously.
I don't care what Binney said.
My personal perception (based on available evidence) is that government crypto is as strong as possible, but is weakened where needed via policies. A decade ago during crypto export limitation, there were no backdoors, but a policy: you may export only keys that long [so we can bruteforce them cheaper].
Another example: SSL is technically secure, but its biggest weakness is trust in a limited list of certificate authorities (CAs) like VeriSign. Then, there is policy that certificate authorities should give up their private keys when FBI/CIA asks for them.
Another example: you may encrypt your files, but must give away your password to a court.
Also, it makes sense economically. Government people need strong crypto like everyone else and the best way to test and verify it is by opening it up and deploying as widely as possible. So mistakes are noticed sooner than later. Then, people with guns will make sure you give up your secrets when they need you to.
I believe crypto systems are alright. It is policies and violent coercion we should be afraid of.
Google.com generates a public/private key pair and has the public key signed by a CA. The signature only says "I verify this public key really belongs to google.com," it does not become part of the actual cryptographic transaction.
Q: Is encrypting my email any good at defeating the NSA survelielance? Id my data protected by standard encryption?
A: Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it.
[1] http://www.guardian.co.uk/world/2013/jun/17/edward-snowden-n...
p.s. I always like this comic about security: http://xkcd.com/538/
One counter example: Clifford Cocks created a public key crypto system before RSA did, and GCHQ kept it secret for many years.
obviously it doesn't matter (decryption still works) as long as it's inside the feistel function itself. so i guess maybe i am just muddling that with how things must be outside that?
Apropos nothing (because I noticed this when looking for another cipher with AND in its round function): to appreciate how simple the design of SIMON (or SPECK) is, read the first (or second) half of the NSA paper... then read the Kelsey and Schneier's Twofish paper.
Indirectly, every decent round function ever created has had AND. At the bit level, you can't have a nonlinear function without AND. The carry bit in additions, for example, is given by a_i&b_i ^ a_i&cin ^ b_i&cin. Using AND directly, though, is pretty rare though not unheard of, since as CPU instructions go AND is doing relatively little work compared to more powerful instructions such as ADD, SUB, MUL, or table lookups. You see AND, though not bitwise, a lot more in hardware-friendly designs that employ NLFSRs as primitives.
As for invertibility, in Feistel ciphers it is not really a requirement, as you point out, f only really needs to be a PRF. That being said, I have heard the argument that making f invertible does preserve information before; I do not know where this argument comes from, and as far as I know it's not formalized anywhere. DES and Blowfish are Feistel ciphers without invertible f, and don't have that bad of a security record.
if you have two random values, using AND biases the number of set bits on average (you get 3/4 zeroes in the output). in other words, it lowers the (shannon) entropy in the circuit, on average, while an invertible function preserves entropy (it has to, right?).
entropy sounds like a smart thing to preserve in a PRF so this would seem like an argument for invertibility.
BUT it's only preserving entropy on average, and what you really care about is the entropy in the difference between input and ouptut in any single round. which is not the same thing at all (identity function is great for the former, not so good for the latter). so you could imagine there's some trade-off...
forgive me if this makes no sense. it just seemed interesting when i thought of it :o)
"Today at the MIT Media Lab Legal Hack-a-thon on Identity we had a great presentation from a couple of designers from the NSA regarding their new lightweight ciphers called SIMON and SPECK. These ciphers are designed for low-power limited gate devices (such as RFID and similar devices).
The MIT Media Lab Hack-a-thon page is here: http://iauth.org
The NSA presentation is here (You Tube): https://www.youtube.com/watch?v=vtyo4nWGBwk
Their paper (PDF) is here: http://iauth.org/legal-hack-a-thon/simonspeckperformance-2/ "
Note: I changed the youtube video from a tinyurl link to the actual link. If you want to tell tinyurl that you visited the youtube video click here: http://tinyurl.com/bf6fbju
[1] https://www.ietf.org/mail-archive/web/cfrg/current/msg03274....