Here’s an IDEA-variant with a 128-bit block length. While I think it’s a great idea to bring IDEA up to a modern block length, the paper has none of the cryptanalysis behind it that IDEA had. If nothing else, I would have expected more than eight rounds. If anyone wants to practice differential and linear cryptanalysis, here’s a new target for you.
Dirk Praet • January 27, 2015 8:56 AM
Two thoughts:
1) Given its origin, we can probably rule out any NSA backdoors.
2) Not sure why they limit themselves to a 256 bit key length instead of 512.
I’ll leave the cryptanalysis to people who are more proficient at it than I am.
Jill England • January 27, 2015 12:01 PM
I’m not sure you can ever rule out NSA back-doors. But if it makes you feel better ok. 🙂
LightBit • January 27, 2015 12:47 PM
My list of block ciphers to avoid (implementing): Camellia, IDEA, MARS and SAFER*
I think I’ve seen 128-bit block Blowfish once.
Dan • January 28, 2015 1:14 AM
While I won’t use IDEA cipher going forward, my GPG key still prioritizes IDEA as the main cipher. It may be old, but it is still pretty safe for texts and emails. Those who criticize it for using arithmetic operations are blowing smoke since 1) Rjindael/AES also uses arithmetic operations, and 2) IDEA and Rjindael are still practically (though not theoretically) secure.
Random • January 28, 2015 2:13 AM
Bruce, few words of your commentary on chacha20, poly1305 and Ed25519 as used in OpenSSH and TLS would be interesting. Relatively unknown ciphers pushed as modern standard in many of the most important projects, especially by Google.
Anura • January 28, 2015 2:17 AM
@Dan
I’m not sure who criticizes IDEA for using arithmetic operations; using all arithmetic operations has the potential for making it a lot easier to implement without side-channel attacks. IDEA however, you have to be careful. Computing the multiplicative inverse mod 65537 can introduce branching, which has the potential for side channels, and the fact that when multiplication is done, zero is mapped to 65536, meaning you have to get clever if you want to avoid branching (a much safer method would be to make “mul(x,y) = ((x+1)*(y+1) mod 65537) – 1” as it doesn’t require branching).
By just adding 1, you would get rid of the potential branching, and then there is actually a really easy way to make IDEA 128-bit without having to worry about the branching in the multiplicative inverse calculation: make it a feistel cipher. Then it becomes very easy to implement using only non-branching code.
Of course, that leaves two things that need to be done: 1) Improve the key schedule (I’ve a relatively simple key-schedule design that would dramatically improve security, see below) and 2) Increase the round; the number of rounds should be determined by the cryptanalysis
What I would do with the key schedule:
So say you need n 16-bit subkeys, n>4, set a zero-indexed array A of n+7 words to the numbers 0,1,2, …, n+6. XOR the first 64 bits of key to the first 4 words, run the round function, XOR A[0] to A[4], and then XOR the next 64 bits of key to A[1],A[2],A[3],A[4], run the round function on those four words, and then XOR A[1] to A[5]. Continue doing this, starting with each position of the array until you have run through all the elements in the array. If you reach the end of the key, start over from the beginning (sorry if the description is not clear, I don’t really feel like writing pseudocode). The key schedule is A[4] through A[n+3].
What I like about this method is that it fulfills several properties that I personally like in a key schedule: 1) it has good psuedo-random properties as long as the round function is halfway decent 2) it can be performed in-place using only a few registers 3) knowing part of the key-schedule does not allow you to determine the rest of the key schedule 4) if you store the last three words that were discarded along with the last word in the key schedule, you can reverse the algorithm, so decryption can be done without having to store the entire key schedule.
Anura • January 28, 2015 3:01 AM
@Random
Ed25519 is just ECDSA using the 256-bit Montgomery curve (aka Curve25519). These are well understood and equal in security to the NIST ECC curves (although Curve25519 is easier to implement and not as likely to be subverted). ChaCha20 is an improved version of Salsa20, and Salsa20 has been around for years and was selected as part of the eSTREAM competition, which was an effort by the EU that underwent a similar process to AES. That said, I would have gone with Salsa20 itself since it’s more well-known.
I can’t comment on Poly1305.
Anura • January 28, 2015 3:06 AM
That should be “a 256-bit Montgomery curve” not “the 256-bit Montgomery curve” as I am pretty sure that there is more than one.
Anura • January 28, 2015 3:17 AM
Actually, it’s not really using Curve25519, it’s using a curve based on that; the point still stands. (I really need to get some sleep)
Gonzo • January 28, 2015 11:01 AM
Here are my thoughts after looking this implementation over.
Each subblock of plain text and each round sub key participates in the MA box, which was in many respects the crucial feature of original IDEA. Each key and each input subblock participates in each output block, in consequence.
One major difference is that the MA box in IDEA was transformed with two of the six round subkeys, whereas this implementation necessarily replaces those subkey inputs at the MA box with input blocks from the periphery rows that were transformed by the addition or multiplication operations with subkeys previously. I wonder if it achieves the same mixing level with this approach.
Years ago, I had a wonderful geek-out session discussing the IDEA cipher with my former father in law before he passed (he was a mathematics and physics guy and a pretty solid mathematician whose grad level book on acoustics is still taught). I came away from the discussion with the impression that he thought the mixing of incompatible operations (addition, multiplication, XOR) was great, but that it was the involvement of multiplication by a Fermat Prime that would be the biggest factor in IDEA’s resistance to various attacks. I remember there was an update of a Lai Massey framework at the time that was working on wider subblocks and used multiplication modulo 2^32+1 (which is not prime) and his view was it would be seriously weaker.
I’m not bashful about saying that I remain a huge fan of IDEA and like a poster above, its still used as the preferred cipher on one of my RSAv4 PGP keys.
That said, these guys have done nothing about the week and related key issues with IDEA (all zero or all 1 keys, for example) that are a function of IDEA’s original very linear key schedule. They also do not seem to have analyzed their subblock swaps and there may be too much parallelism in what they’ve done.
Realizing I’m no where knowledgeable enough to do so, but in the spirit of discussion, if I were to offer advice to the team working on this reboot of IDEA, my suggestions would be:
Of course, I write all this having just read the excellent write up on the “type confusion” vulnerability in the Black Phone (http://blog.azimuthsecurity.com/2015/01/blackpwn-blackphone-silenttext-type.html).
Sometimes, I feel like waxing on about crypto primitives is a waste of time until we can get a better handle on implementation. After all we are blessed with an abundance of strong, well studied, practically unbreakable crypto. IDEA itself is not itself practically broke, nor is Blowfish I should add in a nod to Bruce. Excepting applications with encryption of a ton of data using the same key (where the block size creates problems with birthday issue), each of these are still safe for PGP messages or protection of individual files or small archives. They’re also fine for things like short VPN sessions (Blowfish is still default in OpenVPN) where the data transmitted with the same key does not approach tens of gigabytes.
But its all for naught if the implementations are buggy.
Truly, the crypto world would be served greatly by a portable, cross-platform, programming library akin to LibTomCrypt but based on a programming language that is memory safe. Unmanaged C has had a VERY bad few years in terms of its use in crypto software.
Nick P • January 28, 2015 11:29 AM
@ Gonzo
The implementation issue is a mostly solved problem: CRYPTOL. Work like that can be extended to handle remaining issues. Just another example of IT/INFOSEC not leveraging and building on existing solutions.
Gonzo • January 28, 2015 11:41 AM
@Nick — the problem I see is that Cryptol itself says its not useful for implementation of the whole shebang, such as a complete SSL/TLS suite.
I don’t blame the developers of the BlackPhone for using libscimp — they need to have something they can put to work on various platforms. I just want folks to move past unmanaged C altogether for applications connected to the internet. Its wishful stupid thinking, but good heavens some of these BUGS that are getting through.
A friend of mine (a legal eagle) was telling me about an archaic rule in the law called the rule against perpetuities. Its amazingly complex. Judges have found that its not malpractice to screw it up, but it IS malpractice not to put in the safety clause. Analogizing to crypto I’d say to err is human and expected, but to keep using unmanaged C when you know humans are writing the code is problematic.
Anura • January 28, 2015 2:17 PM
@Gonzo
1. Add the use of a few more subkeys in each round, possibly XOR’d against the inputs to the multiplication operations on the upper left and lower right of the central MA box. Obviously, it would be important to make sure not to break the reversibility of the algo but it does strike me that original IDEA used six subkeys to mix 4 subblocks totaling 64 bits, whereas this implementation uses 8 subkeys to mix 8 subblocks totaling 128 bits — that’s less keymat per sub-block, and less keymat as a percentage of bits processed in each round.
I would probably go in another direction, I would reduce the number of subkeys, and look to make it more nonlinear by replacing two of the multiplications by subkeys with multiplication between two words in the function. Something like this:
x1 = k1*x1 x2 = k1^x2 x3 = k3^x3 x4 = k4*x4 x2 = x1*x2 x3 = x4*x3 x3 = x2+x3 x2 = x3+x2 x1 = x3^x1 x4 = x2^x4
I haven’t tested it, but I suspect if you try it you will find it is a bit more nonlinear and provides a bit better diffusion than the IDEA round function (it’s also fewer operations).
Anura • January 28, 2015 7:24 PM
Just for fun, I implemented a variant of idea based on all of the suggestions I gave above. No clue how secure it actually is, the number of rounds is a parameter and should probably be at least 16, but I just wanted to show that with some minor tweaks IDEA can be made a lot easier to implement securely (specifically, without being susceptible to timing attacks).
Ryan • January 28, 2015 9:01 PM
@Anura
I have a similar idea, using block XTEA or XXTEA where after a round encryption of a section, it would be added with it’s neighbors. It might also reduce some susceptibility to related key attacks (using AES implemented in excel, an appalling few new of subkey bytes are changed when you change a few bits).
Somewhat related question from a non-cryptographer: How much data would you feel comfortable encrypting with a 64 bit block cipher in 2015, assuming CBC mode (CBC seems to be the most common mode for IDEA and Blowfish implementations) and no other practical weaknesses in the cipher design or key size? For argument’s sake, let’s limit it to for file, partition, or full disk encryption, not SSL, SSH, or any other data in transit situation.
I know Applied Cryptography states 34 GB as being the point at which repeated blocks will become likely with a 64 bit block cipher, but I assume one would want some cushion. I’m not sure how much that should be though.
(I know someone will be along to say “Just use AES” or something like that, but that’s not the point of the question)
Clive Robinson • January 29, 2015 10:21 AM
@ z,
<
blockquote>How much data would you feel comfortable encrypting with a 64 bit block cipher in 2015, assuming CBC mode
The answer has a lot less to do with the blockwidth than the mode it is used in. Also of more importance is how long do you want it to remain secret for.
Whilst CBC is quite common it is possible to muck it up, you would be surprised how many people don’t deal with the IV properly, it should realy be selected in a random way, and never reused under the same key, thus requiring either some kind of database or secure pseudorandomness in the design, if “explicit initialisation vectors are used, you don’t have to seperatly send the IV to the decryptor. CBC does not play well with communication or storage errors as due to it’s design errors propergate, it can also have issues with simple message padding as well. It also has the disadvantage that you can only encrypt as a serial process which is a bottleneck in quite a few applications, as it makes it append only not random access.
There are better modes you can use that can also as a consequence improve the length of data you can encrypt however some are encumbered by patents which might be of concern if you need to commumicate with the US or US organisations.
In systems I have control over I prefere to use two or more different algorithms using different modes in series. This tends to overcome the problem you refere to.
@ z,
If you use random IVs and encrypt n 64-bit blocks, then the probability of leaking information to an attacker is less than n2/264, even if the attacker can choose or already knows stuff about some of the plaintexts. (A formal statement and proof of this would be covered in an intro crypto class, and would assume that there are no direct attacks on the blockcipher itself.)
So if you want the probability of info being leaked to an attacker to be less than 1 in a million (say, 2-20), you want to limit n so that n2/264 ≤ 220, which works out to be n ≤ 222 64-bit blocks, or about 32MB. You can set the “1 in a million” to whatever value you consider acceptable, and then do the math yourself. The 32MB amount is obviously rather low in many applications, and although the issue can mitigated by using a different key for each, say, 20MB of data, it is for this reason that 128-bit block sizes are recommended.
Keep in mind that this is a very low bar for “leaking any information”, since the “information” in question could be something as simple as “The seventh 64-bit chunk of THIS desk sector does not contain the same value as the tenth 64-bit chunk of THAT sector.” But it’s usually best if you can avoid having to guess what info will be leaked and what an attacker could do or infer based on that info.
Note that the only part of this answer that could make the “…in 2015” part of your question matter is the part about the blockcipher itself being secure. If the blockcipher uses 56 bit keys, it’s probably not secure in 2015.
Anura • February 3, 2015 12:48 AM
@s
I believe what the previous poster was referencing is that you do not want to allow two blocks to repeat, as this causes a problem in all modes of operation. The probability that a block will repeat is 50% once you have encrypted about 2n/2 blocks with an n-bit block size. In output feedback mode, it’s particularly bad because you can’t guarantee that a block won’t repeat and if there is any repetition then all subsequent blocks will be repeated and you end up with the stream cipher problem, however if your data appears sufficiently random then the attacker might not be able to determine there is an issue. With CBC mode, having two blocks encrypt the same tells you that they are identical except they may be XORd to different known value, you may be able to guess the other. With CFB mode you can determine that two blocks of ciphertext are identical, however they may not repeat.
Counter mode makes it easy to mitigate the problem: deterministic IVs. For a 64-bit IV, you can take some of the bits, and have a fixed identifier so that know two devices with the same key have the same identifier, a global counter that is not allowed to repeat, and then the rest of the bits are used for the normal counter operation (which is 0 for the first block). The counter bits limits the data to 2cn/8 bytes of data per key/global counter combination, and the global counter limits the total number of connections that can be encrypted. If you have an 8-bit identifier, 20-bit global counter, and 36-bit normal counter, then you can encrypt 512 gigabytes. The specification for GCM mode describes this way to do deterministic IVs, unfortunately they limit the counter to 32-bits regardless of whether you are using random or deterministic IVs, limiting the amount of cihpertext per IV.
Counter mode also avoids the problem if you never reuse keys, e.g. if you are doing a key-exchange for each connection, you don’t have to worry about how much you encrypt since the keystream is never going to repeat. However, there is the issue in that you will be able to distinguish the ciphertext from truly random data in a chosen plaintext attack. Whether that leads to a feasible attack is another story.
The best solution is to just not use 64-bit block ciphers. Use 128-bit block ciphers, and it’s no longer a problem. I take that back; it’s possible to create realistic scenarios involving massive amounts of data where it may be too much of a risk; this is a good reason to start looking at 256-bit block ciphers.
Although I’ve played with one really ridiculous and slow cipher design in the past that generated a separate key-schedule for each block based on a nonce, a counter, and the key, which prevents any of the problems mentioned as long as the nonce isn’t repeated. It was a fun design, a 256-bit block size, 256-bit key, 256-bit nonce, and 256-bit counter; it was a feistel cipher with the feistel function performing a 2×2 matrix multiplication modulo 2^64 against a static matrix, followed by multiplication in GF(2^128) by a key-dependent value that changed each block, followed by addition modulo 2^64 to 2 64-bit subkeys. Computing the key schedule was done by first multiplying the counter by a 4×4 matrix, followed XORing the nonce, followed by multiplication of each half by a different constant in GF(2^128), followed by muliplying again by the matrix, followed by XORing the key, followed by multiplying each half by another constant in GF(2^128). Then there was a counter for each round that it was XORd by, then there was addition mod 2^64 by a static value computed from the key and nonce in a similar fashion as the block-specific key value (but with no counter), then muliplication in GF(2^128), then the 4×4 matrix again, followed by one final mutiplication in GF(2^128) with a constant that differed with each round – one half was the key that was added at the end, and the other was used for the multiplication in GF(2^128) except with the highest bits set to 0 (for simplicity/performance reasons) and the next highest bit set to 1 (to guarantee no multiplication by zero). Like I said, ridiculous and slow – but fun to design, and it can encrypt everything in parallel. Another feature was that it take the ciphertext that results from running half the rounds, XOR them all together, and when all data was encrypted, it would then encrypt that value, which could be used as a message authentication code.
Subscribe to comments on this entry
Sidebar photo of Bruce Schneier by Joe MacInnis.
Guest • January 27, 2015 7:32 AM
The use of arithmetic operations for ciphers has been criticizes on a very general level. This was taken into account in the design of IDEA-NXT, the official successor of IDEA, which supports 128 bit block length (but, like all IDEA variants, is patented). This proposal is a step backwards.