6 ms·
The SIMON and SPECK Families of Lightweight Block Ciphers
- vertis 13y agoI must be paranoid now. My first reaction was "It's a trap!".
- csense 13y agoPeople 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." [1] http://en.wikipedia.org/wiki/Substitution_box http://en.wikipedia.org/wiki/Substitution_box
- vertis 13y agoI was too young to be a participant, however I do remember reading about all the happenings around crypto in the 80s and 90s. It's healthy to suspect crypto systems because of their role in protecting us.
- EthanHeilman 13y agoWell also the fact that they shrunk the key size of DES from 128 bits to 54 bits while DES has a 64 bit block size.
- devin 13y agoHa, more likely a recruiting tool! Reads Article Checks Email "Hello! We are looking for programmers with an understanding of the SIMON and SPECK families of lightweight block ciphers."
- vertis 13y agoWell 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.
- ars 13y agoI had the same though, but the NSA is actually the one who published, or vetted, most of the encryption tools in common use today. (DES, AES, SHA1, etc)
- jlgreco 13y agoWhat are some other examples of "lightweight" block ciphers? Is AES considered lightweight, or are these far "lighter"?
- tptacek 13y agoTEA 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.
- JoachimSchipper 13y agoI'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.
- tptacek 13y agoYeah, I wasn't thinking straight about that either. :) 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.
- csense 13y agoIt's ironic that the PDF download is called 404.pdf. When I saw the name, I thought the link was broken and their error page was a PDF.
- deleted 13y ago[deleted]
- tptacek 13y agoThis 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.
- csense 13y agoI 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.
- EthanHeilman 13y agoNo one knows but the NSA may have a budget of twice that. "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-surveillance-cost/index.html http://money.cnn.com/2013/06/07/news/economy/nsa-surveillanc...
- oleganza 13y agoRecent 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.
- DanBC 13y ago> 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.
- dfc 13y agoYou think Joan Daemen and Vincent Rijmen work for NSA?
- doe88 13y agoHowever 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.
- andrewcooke 13y agois 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?
- tptacek 13y agoRogaway's SEAL also used AND. 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.
- pbsd 13y agoThere 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.
- andrewcooke 13y agoi 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)
- dfc 13y agoFor 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). The MIT Media Lab Hack-a-thon page is here: http://iauth.org http://iauth.org The NSA presentation is here (You Tube): https://www.youtube.com/watch?v=vtyo4nWGBwk https://www.youtube.com/watch?v=vtyo4nWGBwk Their paper (PDF) is here: http://iauth.org/legal-hack-a-thon/simonspeckperformance-2/ 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 http://tinyurl.com/bf6fbju [1] https://www.ietf.org/mail-archive/web/cfrg/current/msg03274.html https://www.ietf.org/mail-archive/web/cfrg/current/msg03274....