The SIMON and SPECK Families of Lightweight Block Ciphers
eprint.iacr.org
eprint.iacr.org
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.
One counter example: Clifford Cocks created a public key crypto system before RSA did, and GCHQ kept it secret for many years.
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/
"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....
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)
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.
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.
Deleted comment
"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.
"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."
It's healthy to suspect crypto systems because of their role in protecting us.
(DES, AES, SHA1, etc)