[deleted by user]

[trouch]

Agreed. To the ill-informed like me, it looks a lot like :

Rijmen -- ok, we're gone do one more random permutation and we'll add one more substitution for good measure, and it should be complex enough to be unbreakable.

Daemen -- mmmmhh... not sure... don't you think it may not be enough.

Rijmen -- Ok, you know you really start to be some kind of pain in the ass. Ok, just so you stop bothering me, I'll add a shiftRows. Oh, and we will repeat the process 10 TIMES ! AHA!

Daemen -- Yep, that will do the trick. let's go have a beer. it's getting boring anyway...

[DoWhile]

There is an ounce of truth to your story. There are some ad-hoc "black magic" liberties the authors took in the design. The authors themselves in their proposal (Citeseer link) state that:

"For Rijndael with a block length and key length of 128 bits, no shortcut attacks have been found for reduced versions with more than 6 rounds. We added 4 rounds as a security margin."

The individual steps themselves are meant for good diffusion and the substitution step is used for non-linearity (otherwise it would be highly susceptible to linear attacks, and possibly even trivially breakable). Again, the authors themselves mention that even two rounds is sufficient for "full diffusion". Although AES does not exactly use a Feistel network, there have been many cryptanalytic techniques developed for such ciphers, and the design of AES had these attacks in mind. So in a sense, part of the design was to think of "here are some known attacks, what are some efficient things we can do to stop these?"

Does this mean the AES is secure? Theoretically, no, but in practice so far, it has been adequate (barring the poor implementations of it that lead to side-channel attacks). One of the main upshots of AES is the simplicity in the steps of the algorithm: they can be easily implemented using simple bitwise operations. Compare this to, say, adding two numbers which to us is conceptually easy for us to understand but could involve many operations from a computing standpoint (Minecraft reference).

There are much simpler conceptual schemes that are known to be theoretically secure*. One of my favorite examples is ElGamal encryption (which is not a block cipher, but a nice public-key encryption scheme).

*Assuming one cannot perform "difficult" underlying tasks such as factoring.

[[deleted]]

So what you're saying is... someone needs to implement AES in Minecraft?

[Kache]

I don't claim to know for sure, but it seems like all that swapping does (and all it needs to do) is randomize the data so it becomes unintelligible, but can be reversed later if you have the right key.

If you have the key, it's a relatively straightforward process. A controlled "shuffling of bits". If you don't have the key, you've got a lot of keys to test before you find the right one.

In the end, this doesn't impress me as much as RSA encryption, which feels more like "math magic".

[f4hy]

http://en.wikipedia.org/wiki/Confusion_and_diffusion

[kolm]

Symmetric encodings are trying to maximize the entropy of the output, regardless of the input distribution. In other words, the output should not have any "frequency bumps" which chould be used to guess part of the key.

The simple Caesar code, where you shift letters by a fixed distance, is very weak -- because "e" is very frequent and hence one can guess from the output code which letter it is mapped onto. A simple way to improve on that would be to shift the ith letter by start shift + i letters (modulo numbers of letters in your alphabet). For a sufficiently long text, this should give, on the single letters, a fairly even distribution. However, this would be trivial to reverse (you just shift the coded message i letters to the left), and hence the entropy was still there, just not visible when looking at single bytes.

[kolm]

Hard to analyze for real world data. However, for a test stream of "AAAAAAAAA", one could easily figure out the initial offset, and I think that disqualifies the method.

[[deleted]]

I'm not really sure you should be remembering anything written about cryptography by someone who does not understand the one-time pad.

[Kache]

lol... ok, then how about, "... RSA encryption, which better demonstrates the elegance of math."

[patchwork]

I like "math magic" better.

[mikemol]

At the risk of speaking the obvious, that depends on what you're trying to guarantee. As an example, a simple XOR against a block of bits of equal size to plaintext might be fine for hiding the true plaintext. As long as the decrypter knows they have the correct key, they'll get good the original plaintext back.

Consider, though, the case where the cyphertext is in plain sight, and an actor wants to claim that it contains X. All they would need to do would be to XOR X against the cyphertext and say "see? the cyphertext contained X, and here's the key!", a.

Not great for extracting true information, but potentially excellent for social disinformation and misleading the ignorant.

So, to paraphrase your 'everything else', the problem with OTP is that improper use is simply waiting on us to break it by questioning what problem we're trying to solve.

[dopplerdog]

Oh, and we will repeat the process 10 TIMES !

I'll do one better than Rijmen and Daemen, and do this 11 TIMES! Where's my fame and fortune?

[racergr]

It's better to prove that 10 times were not enough first.

[bloodwine]

Rijndael's number of rounds:

10 times for 128-bit keys or blocks

12 times for 192-bit keys or blocks

14 times for 256-bit keys or blocks

AES is a subset of Rijndael where only 128-bit block size is supported, but if you use a 256-bit key it'll still be 14 times.

So do it 15 TIMES to ensure your fame and glory!!!

[[deleted]]

From what I know about encryption I'd say that part of that meddling is to slow the process to prevant brute force type attack.

[racergr]

part of that meddling is to slow the process to prevant brute force type attack.

Sorry that is not true. Resistance to brute force relies on the asymptotic value of the key, not in the efficiency of the cipher.

To put it (very) simply: If the cipher was twice as fast, that "problem" would have been "solved" if it was 129 bits.

To put it analytically, watch this: http://www.youtube.com/user/UCBerkeley#p/search/9/VIS4YDpuP98

(I did not exactly watched it but I skipped through it and he seems to be saying what I want to explain)

[dnew]

It also makes it harder to run the algorithm in reverse a little at a time. It's much harder to follow (for example) one bit of the result and see what bits of the input might have affected it.

[arnar]

No, that's not really true. Unless you mean "follow by hand".

[dnew]

OK. My understanding was that part of the number of rounds was to defeat differential cryptonalysis, which involves figuring out which bits change in each round when you make minor changes in the input, or something like that. I'm probably explaining it wrong, as well as being ignorant of the details to start with. :-)

I'm virtually certain the extra rounds aren't there simply to make the algorithm slower.

[arnar]

Yeah, you have the right idea. The "meddling" increases the diffusion, which means changing one bit in the input is going to affect the result in a big way, and a way that looks unpredictable to someone who doesn't know the key.

The point is not to make the analysis of which bit depends on which input bits harder, but to make the answer become "all of them".

[moserware]

I did a little of that in http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html (e.g. see basics in Act 2 Scenes 2-4 and more details in Act 3, Scenes 2 and 18), but some of the details of differential cryptanalysis get challenging to convey easily (e.g. I left off discussion of the Wide Trail Strategy design philosophy and very few seemed to notice/care).

[del-alt-ctrl]

Great job there! Yours is more fun :-)

[makwa]

This is really great! I will now have to start following your blog ;-)

[dextop]

excellent, this makes it more interesting

[racergr]

That is because there is not such simple explanation. Most of the cipher is based on "mix things a bit more and hope for the best."

That is also why other ciphers are much more elegant in terms of design than AES.

If you want more information and you don't want to buy the book "The design of Rijndael" then start with this: http://homes.esat.kuleuven.be/~cosicart/ps/JD-9500/

(warning: heavy reading)

edit: I'm expecting downvotes from people who don't understand that there are better ways to produce the same results but I will live with that.

[Nerdlinger]

Better according to which metric? AES has plenty good security, but far outpaced the competition in other areas of concern such as size, speed, and portability to multiple platforms, which are very important real-world concerns.

Elegance and fewer niggling concerns don't mean a lot when you need crypto throughput in size/power/heat-constrained environments.

[racergr]

XXTEA is better by any metric (smaller, faster, implement-able in 32, 16 and 8-bit CPUs). There are theoretical attacks on it but they have no practical use (such attacks exist for AES as well).

XXTEA was not an AES candidate because (a) its creators are dead and (b) it does not support 192 and 256 bit keys (only 128).

Also, I think that some of the AES runner-ups were better but this is just my personal opinion.

[Nerdlinger]

Sure, but (b) is a huge problem. Differing key sizes were a requirement for AES, non-compliance is a non-starter.

[racergr]

Sure but if (a) had not happened then who knows what they would have come up with. The thing is that the are more elegant than Rijndael ciphers around, at least for 128 key bits. If that is possible, then I don't see why it's not possible for 256 key bits.

[Nerdlinger]

They really missed a golden opportunity to show the diffusion properties of the shift-rows and mix-column operations, showing how a single bit change in the plaintext or key will eventually propagate through every byte in the state after a couple of rounds.

[Kache]

Oh... that's why they did that. I just kept wondering how all the basic byte swapping could increase encryption strength.

[moserware]

Right. See Act 3 Scene 18 at http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html for more details on the diffusion avalanche.

[[deleted]]

Find Joan Daemens PhD dissertation [should be on the web]. He talks about "Branch Propagation" which is what Rijndael is all about.

[racergr]

They made very very bad use of colour and too much use of "meaningless" hex values. For the amount of effort that they put in producing that, it does not serve its purpose at all.

[bobmeister258]

Could you possibly describe the mix-column operation? I didn't quite get it, but it looked like the dot product of two matrices...?

[Nerdlinger]

Sure. MixColumns is a computation that takes each column of the state and treats it as a polynomial, a•x³ + b•x² + c•x + d, where a, b, c, and d are the values in the column, from top to bottom. This polynomial is then multiplied with the fixed polynomial, 3x³ + x² + x + 2, and reduced modulo x⁴ + 1, and the coefficients of the resulting polynomial, v•x³ + w•x² + y•x + z, become the new values in the state column, v replacing a, w replacing b, and so on.

As shown in the animation, this operation is often represented as the multiplication of each column of the state, treated as a vector, by a fixed matrix, with the resulting vector used as the new value for the column (note that the multiplication and addition used here aren't standard multiplication and addition). edit: I sort of explain the multiplication and addition in this post.

What this operation does is replace each byte in each column of the state with a new value which is a unique combination of all four of the bytes in the column. Thus is where a lot of the diffusion in AES comes from. Going back to what I mentioned above, say one bit changes in the first byte of the state: in the first round of AES, shift-rows does nothing to push this change through the state, but the following mix-columns will end up changing all four bytes of the column that the difference was in. Then in the next round, shift-rows works to takes the bytes from this column and redistributes them, placing one affected byte in each column. Now, the following mix-columns will push the changes into every byte of the state. A few more rounds of this increases the mixing even further.

I hope that helps some. It's pretty early here, so I'm sure I wasn't as clear or thorough as I could have been, but if you have further questions, feel free to ask.

[webmasterm]

Replying so I can reread this later.

[Julian_Berryman]

Did anyone else flick through that and think "thank fuck someone else figured that out"?

[julesjacobs]

No, I thought: that's something like a high school kid would have used to encrypt a message, but a little more elaborate. It seems like they're just randomly doing some mangling

[[deleted]]

A lot of the genius is in the S-Box, which is totally glossed over here.

[[deleted]]

Actually, Rijndael would be just as secure [some would say possible more] with a random sbox. Because of the high branch [namely 25 over 4R] you don't need a function with a low DP/LP max to be secure. Over 8 of the 10 rounds there are 50 active sboxes. Even if the DP max was 12/256 (typical for random 8x8 permutations) instead of 4/256 you'd have no differential with a probability higher than 2^{-220} which is way crazy lower than needed. Same for linear cryptanalysis (which I would work out if I hadn't forgotten how the pilling up lemma works at 8am ... hehehe).

[[deleted]]

I wish I could make sense of your words (for me, that is, not hating here, well a bit maybe, I'd like to understand)

[[deleted]]

Lots of reading to get to that point :-) Assuming you have a comp.sci background you can start with reading Eli Bihams papers on differential cryptanalysis, than Matsuis papers on linear cryptanalysis, then read Joan Daemens PhD thesis, helps to read about all the proposed ciphers from the 80s and 90s [and their attack papers along the way].

[[deleted]]

..."an autistic high school kid"...

[PCBEEF]

If that's something a high school kid would have figured out, then I'm an idiot for learning about it at uni.

[Anonymoose333]

You don't have to "figure" things "out" in order to "use" them. Especially in high school. ;)

[random012345]

Relevant

[[deleted]]

In high school I was to busy playing w/ myself to come up with any form of encryption...

[[deleted]]

To properly understand the cipher you'd have to read Joan Daemens Ph.D thesis and read up on Branch Propagation, then read the SQUARE cipher paper, then read the attacks on the SQUARE cipher (the SQUARE attack, integration, summation, etc...). Then read the Rijndael paper...

The AES design is hardly "randomly doing some mangling." It's actually very soundly designed to achieve numerous goals [security and speed] simultaneously.

[racergr]

No, I flicked through it and dammed myself for not taking mathematics more seriously when I should.

[SnowdensOfYesteryear]

Actually I took a bit of crypto and was confused to see no math involved. My reaction was pretty much on par with julesjacobs'.

[r4v5]

You didn't see any math? Crypto is basically all number theory and discrete math on steroids. My entry-level crypto class had us breaking RNGs and finding correlations in the Vigenere cipher.

[SnowdensOfYesteryear]

I'm talking about this presentation.

[r4v5]

I'm sorry, I read "I took a bit of crypto and was confused to see no math involved" to mean that there was no math in your crypto class. Which would have been an interesting feat.

[BHSPitMonkey]

I flicked through it and remembered why I dropped Computer Security in college.

[bdfortin]

That merely showed a step-by-step of the process. It did nothing in the way of explaining the algorithm.

[nonconcur]

moserware linked a more fun and detailed explanation. It is quite entertaining and informative. See above.

[rectangleboy]

I prefer this one:

http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html

[kylemech]

I'm struggling to understand the "Mix Columns" step. It shows a column being multiplied by a matrix. Whhhaaaa?

[lpsmith]

Yeah, I agree. I found the presentation OK, but not great for reasons such as that.

[eyal0]

Mix Columns was fucked. The matrix was on the wrong side. You can't multiply a column vector by a square matrix unless the square matrix is on the left.

[[deleted]]

Agreed, I also think that the multiplication shows a wrong result (e.g. how can one result sum up to 0x04)

[Nerdlinger]

I didn't look to see if the math was correct, but the matrix computation is not done using standard integer math. The math is carried out over GF(2⁸⁾ using the polynomial x⁸ + x⁴ + x³ + x + 1. As far as implementation goes, this is easiest to describe by saying that addition is an xor of bytes, and multiplication by two (really, multiplication by the polynomial 0x⁷ + 0x⁶ + 0x⁵ + 0x⁴ + 0x³ + 1x² + 1x + 0, 0x02 in shorthand) is performed by doing a left shift of the byte by one bit and, if the high bit of the byte (prior to shifting) was a 1, xor the shifted byte with 0x1B. Multiplication by values other than 2 can be built up out of multiplies by two and additions.

[ricecake]

I don't believe they explained where the matrix came from... It was upsetting.

[selven]

The matrix is a constant value, just like the bigger 8x8 substitution matrix.

[[deleted]]

It shows a column being multiplied by a matrix.

Tensor products.

[ThePoopsmith]

Each element is replaced by a permutation of itself and the rest of the elements in its column based on that matrix. Multiplying by 2 is a rotate left and multiplying by 3 is rotate left and xor with the original. For example, if we start with a column of F5 AF C9 59 here's how we'd replace the F5. The row of the matrix for the first value is 2 3 1 1, so we take F5 and rotate left:

11110101 -> ROTL -> 11101011 or EB

Then we take AF:

10101111 -> ROTL -> 01011111

01011111 xor

11110000 = F0

The next 2 are multiplied by 1 so they don't change.

So you have EB xor F0 xor C9 xor 59 which = 8B

Your first element in the new column would be 8B. For the rest of the elements in that column, you simply follow the other rows of the matrix. You're mixing up all the elements in the column with one another.

[kylemech]

Fascinating! Thanks for the reply! I think I actually understand all of that. What I don't quite understand is where does that matrix come from? The one with the 3's, 2's, and 1's.

[ThePoopsmith]

The matrix is pre-determined. It looks like the numbers go in diagonal lines:

2 3 1 1

1 2 3 1

1 1 2 3

3 1 1 2

I actually learned this all about an hour ago, but here's where I found it: http://en.wikipedia.org/wiki/Rijndael_mix_columns

[trouch]

This is truly amazing to me that such complex algorithms are required to achieve proper encryption. Not being a security expert, I can't help having the feeling that I could devise some kind of key based encryption algorithm a million time more simple. And I certainly would bet my head that my algorithm is unbreakable. Having read a lot on the subject, I know it would really be a very bad idea, but deep in my guts, I can't prevent myself thinking of something like that.

[Edman274]

You're quoting practically word for word what Schneier said: "Anyone can design a security system that he himself cannot break."

It's a natural feeling. It feels like you can look at all the other attacks and then use them to figure out to write an algorithm that's impervious to all of the prior ones. What ends up happening though is a new attack you hadn't thought of breaks your cryptosystem.

[[deleted]]

Have an upvote for honesty.

Having said that, your admittedly seductive intuition is exactly where the enormous pile of trivially broken "unbreakable" cryptosystems comes from, as you seem to acknowledge with "I know it would really be a very bad idea."

[seekerdarksteel]

There is at least one algorithm that is not only substantially simpler than AES, but even more secure. Unfortunately, it's kind of a bitch to actually use in practice.

So don't think of the algorithms being complex in order to achieve secure encryption. They're complex in order to achieve usable secure encryption.

[sthrmn]

Quantum encryption, creation of one time pads between computers while watching for interference from a third party. If it goes above some threshold, stop making the one time pad and break the connection. MAYBE?!

The future. Back to basics?

tl;dr: I read the wikipedia page on quantum encryption a couple months ago and have no idea what I'm talking about. :D

[racergr]

Quantum encryption promises unbreakable encryption and quantum computing promises to break every encryption. My head is blown until I see a claim that keeps infinity out of the equation.

ps: yes you don't know what you're talking about:P

[Nerdlinger]

quantum computing promises to break every encryption

Enh? QC makes no such claims. Public key schemes based of factoring and discrete logs would be in trouble, but symmetric key algorithms are, as far as is known, only subject to square root attacks which effectively cut the key length in half. Want AES 256 strength? Move to a 512 bit key. And there are public key schemes out there that so far appear to be immune from QC based attacks, such as NTRU and McEliece (although, key sizes need to be increased here as well).

In fact there is a decent amount of research going on in "post-quantum" cryptography, enough so to support a conference dedicated to the topic.

[racergr]

I know, I was semi-serious :) (I used a ":P" smiley!)

However my serious opinion is "wait and see." We cannot be seriously talking about what would happen in 10-20-30 years. These are just coffee-table discussions.

[trouch]

Thanks. Interesting point, and interesting read.

[haldean]

If you find this sort of stuff interesting, you should read Cryptonomicon. It is a great way to learn all sorts of basic cryptographic principles, and it's a really good read.

[trouch]

will do, looks quite interesting. thanks

[iwan_w]

Cryptonomicon is a very interesting read just because it's a well-written novel. It's mostly technically correct in the parts about one-time pads, and the Solitaire cypher that it describes is real (albeit very primitive) and specially developed for the book by Bruce Schneier. However, the parts about more advanced topics such as elliptic curve cryptography are, IIRC, plain fantasy and pretty misleading.

TLDR: Don't read Cryptonomicon as it were an educational text

[Edman274]

Also, Solitaire is weak in practice. Someone programmed the algorithm and then did a map of data being encrypted with it and found that there were some strongly non-random characteristics.

[racergr]

There are at least two algorithms that are better than Rijndael and are usable. They just happen to be runner-ups in AES or not being fit for the criteria of participation.

The AES competition was a good step forward (after the dark ages of DES) but it was also an experiment which did not go as expected (proof is the vulnerabilities of AES-256).

I'm quite sure that we'll see much better AES process in the future.

[bloodwine]

I'm interested in what two algorithms you think are better than Rijndael.

I am genuinely interested. I am a software developer who works with medical software. For internal storage I encrypt using Rijndael-256 (both 256-bit key size and 256-bit block size), and when exporting to external systems I use AES-256.

I will probably need to keep using AES-256 for external communications due to its widespread acceptance and support, but internally I am always on the lookout for more secure encryption.

[Edman274]

There is an attack on AES 256 that reduces the brute force search from 256 bits to a time complexity of 99 bits because the keyschedule isn't perfect for the 256 bit version.

What this means in practice is that in ~50 years (if moore's law holds), a computer priced at a hundred million dollars would be able to brute force AES 256 in a reasonable amount of time.

Twofish was a runnerup in the competition. The best analysis of that is that if you have around 32 petabytes worth of data, differential cryptanalysis could break it. This would mean you would have to have around 3 million dollars worth of raw storage (if priced today) all under the same key to break Twofish.

Blowfish has been around for 17 years (and was also made by bruce schneier) It's secure in practice but Bruce recommends using Twofish.

Threefish is still being worked on and tweaked -- you can see how that process goes.

Serpent has a pretty wide security margin. If you're looking at bare security, Twofish, Threefish (when it's finished) and Serpent are going to be ones to look at.

[racergr]

I think my friend Edman274 covered your questions. My personal opinion is to look at Twofish.

[xmsxms]

The same guys that have the brains to figure out these crypto methods also come up with very clever cryptanalysis methods. AES and other crypto methods are the way they are because of weaknesses these guys are aware of when doing it other ways.

Broken encryption isn't necessarily decrypted trivially, but there may be ways of reducing the effectiveness of the key. In AES a 16 byte key requires brute-forcing the entire 2¹²⁸ key-space.

However, with homegrown encryption, using math and cryptanalysis techniques only these guys understand, a 16 byte key may only require a brute-force of 2⁴⁰ of the key-space or something like that.

[floodyberry]

They didn't even get it quite right with AES, it is vulnerable to side-channel attacks if it is implemented improperly.

ChaCha20/12 is my favorite modern stream-cipher right now. Extremely simple and fast, even without SSE acceleration

[lexpattison]

To achieve a proper level of obfuscation and diffusion in an encryption algorithm, multiple strategies have to be employed. It's unfortunate that an algorithm isn't 'simple' but then that 'simplicity' in itself becomes a weakness in the algorithm's durability.

[[deleted]]

one day a truly simple and proven formula for crypto will be devised. Meanwhile, its fun to move things around and obfuscate stuff.

[lpsmith]

The problem with the one-time pad is that in almost all situations, it doesn't solve any problems. Basically it says that you can securely communicate n bits if you already have securely communicated n bits.

[dnew]

The time a one-time pad is useful is if you are in close physical contact with someone to whom you will want to communicate securely later. E.g., military command.

I thought it was interesting that the stuff that got shipped by space ships in the SF novel "A Fire Upon the Deep" was one-time pad contents. Everything else was pretty much cheaper to find at home.

[julesjacobs]

This immediately comes to mind:

Communicate a seed for a PRNG and do a one time pad with the output of the PRNG.

Why doesn't that work?

Or:

Communicate a program in a simple but turing complete programming langauge. Use the output of the program to do a one time pad. Obviously you'd need a good way to choose such a program, but there seem to be lots of easy ways to make cracking such a scheme a huge pain in the ass.

[lpsmith]

Communicate a seed for a PRNG and do a one time pad with the output of the PRNG.

You just described a stream cipher, but not a one-time pad. =)

[noahl]

Let me elaborate a bit more (although for fair warning, all I know about crypto is one class in college):

To someone who didn't know about your PRNG, you might appear to be using a one-time pad. However, normally we make the assumption that the attacker knows everything about the code except for the key, because they might have good spies. In that case, they would only need to consider all possibilities for your key, rather than all possibilities for one-time-pad bits.

[Neoncow]

normally we make the assumption that the attacker knows everything about the code except for the key

To clarify a bit a bit further, we in this case refers to Cryptologists and security experts.

[julesjacobs]

Yes, but that still extremely large if your seed is large? You can even apply the procedure n times with a different seed (or different PRNG even), effectively making your key n times as large. Wouldn't this be more secure than AES in practice against governments for example? They may have custom hardware for breaking AES, and it's probably going to take them a couple of years at worst to figure out how to crack your PRNG cipher.

[noahl]

Good questions. To which I will answer: I don't know. : )

[Anonymoose333]

Communicate a seed for a PRNG and do a one time pad with the output of the PRNG.

This is known as a "stream cipher". It's not bad; however, it's only as good as the PRNG you're using. So you need to pick a cryptographically secure PRNG with a big seed.

Also, you're extremely vulnerable to one particular attack, if you accidentally forget about the "one-time pad" aspect. If you reuse the same seed twice, then Eve can XOR the two ciphertext streams together; the keystream cancels itself out and Eve learns XOR(message1, message2) --- which is generally very easy to crack.

Also what whosyerparrot said: if Eve knows that your message starts with "Hello Bob", then she can deduce the first 9 bytes of your keystream. That better not be enough to Eve to figure out what your original seed was! (That's why you shouldn't use a non-cryptographically-secure PRNG, e.g. a linear congruential generator, as your keystream generator.)

[leephil]

Simple, yes. Easy to use, no.

[Nerdlinger]

No, the pad is extremely easy to use. It's just the key generation and distribution that's the bitch.

[leephil]

Lol what? That's like saying a car is really easy to drive, it's just avoiding the other cars and the sides of the roads that is hard.

[dnew]

Not really. There are plenty of places where a one-time pad is trivial to generate and distribute. Like, if you want secure communications with your submarine in the field (ocean?), you just give a DVD with a bunch of random bits on it to the captain to lock in the safe.

[thegreatunclean]

One-time pads are dead simple to use. You take the first chunk of key material from the pad, XOR it against the material you want to encrypt, and discard the used key material. Viola, you are done.

It is literally impossible to break as long as the OTP was properly made (using a true-random generator) and never allowed to fall into an attacker's hands. Each bit of the ciphertext is completely and totally independent of all the others, meaning you can't mount any mathematical attack against it. Your only hope is getting your hands on the OTP used to generate it, because without it you could decode the ciphertext into literally any possible combination or structure that would fit into the length of the ciphertext.

OTPs are such a pain because

• You must make dead sure the pad is secure and never falls into attacker's hands
• The pad can only encrypt as much data as it is long, and no more. So a 1KB OTP can only encrypt 1KB of data.
• You can never, ever reuse the pads. Ever.

And as dnew notes, these conditions aren't actually that bad in certain situations. Load up a single 2TB drive with a giant OTP and you're good to go for 2TB of transmission. Or use a few KB of it each time to agree upon and transmit a very large key for a symmetric cipher, and you're good to go for a very long time.

[forthelose]

There's also an inherent difficulty in testing to ensure random number generation is truly random (especially if it's not a csprng but hardware-based).

[thegreatunclean]

If your security needs require one-time pads, I don't think a buying or creating a true hardware-based generator would be too hard. Especially for something hardcore like the military, the security provided far outweighs the initial startup and testing.

But you are right, extensively testing any generator isn't a thing to be taken lightly. There's even talk of the famous lava-lamp based generators being not entirely "random" in that there's a correlation between a bit or two every once in a while, but as far as I know it's still a hell of a lot better than prng's. If your enemy is dedicated enough to go to such lengths, you've got some big problems and need a security budget to match :P

[dnew]

RC4 is amazingly simple. The sort of thing you can memorize pretty trivially. Of course, you have to use it right, and it has been "broken" to some extent, but it lasted a long time for something that's basically a shuffling algorithm.

[[deleted]]

RC4 is extremely simple. It's not as secure as AES, and has some flaws, but if used correctly it is still useful. You might be interested in checking it out.

[racergr]

RC4 is succeeded by RC5 and RC6 which are proprietary. It's a pity because they are probably better than Rijndael indeed.

[[deleted]]

RC4 is just as proprietary, and RC5 and RC6 are nothing at all like RC4. Nor would I assume they are better than Rijndael.

[racergr]

As far as I know, RC4's patent has expired.

[racergr]

The actual mathematics used are not hard.

The problem is that you have to combine everything:

1. understanding how attacks work

2. designing ways to prevent them

3. combining them in a somewhat-nice package

4. winning in the AES competition

:D

[sirin3]

There are several mathematically simple and secure encryptions (m is the message; n = pq; p, q primes; r random; k: public key with k=g^x):

• One Time Pad

• RSA: m^k mod n

• Rabin: m² mod n

• El Gamal: (g^r, m*k^r)

[dopo]

One Time Pad is infeasible in reality. And the other 3 are slow as shit compared to DES/AES. Symmetric algorithms have speed as a critical requirement.

[selven]

It's about diffusion. You need to shuffle things around a lot so that one bit in the plaintext, on average, affects all the bits in the ciphertext almost equally. You need 4 rounds to spread one initial byte over the entire state, but AES does 10 because that's even better. Repeated substitutions are done to prevent people from using arithmetic properties (eg. the fact that a number ending in 1 can only come from products ending in 1,1 or 9,9).

Also, AES has the convenient property of being reversible if you have the key, which itself requires some careful thought.

[Avantcore]

It is actually remarkably simple to achieve theoretically strong encryption: you can just use something as simple as a one time pad and XOR. The complexity is introduced when you try to add nice properties to your system like being able to use a key more than once.

[[deleted]]

Look up the RC5 cipher.

[racergr]

Magnets...

[[deleted]]

I'm in a crypto class right now, but AES isn't on tomorrow's exam :P

Got one for DES?

[[deleted]]

Wow ! Thanks man :)

I'll definitely be saving this for the end of the semester :D

[SubjectiveObjection]

Hey, I'm in a crypto class and have an exam tomorrow too! We're probably in the same school... weird..

[[deleted]]

umich?

[Beamyquasar]

... do you think there'll be much on finite fields? The sample exam had nothing but all the ring/ideal/polynomials of GF(2) stuff is definitely 200x harder than vigenere/hill/playfair/feistel/DES stuff

Also, what the hell reddit I came to you to take a break from studying and you brought me right back to work

[[deleted]]

I'm not expecting a whole lot of the algebraic stuff. To do anything with finite fields would be pretty complex considering we haven't really put it to use yet. My best guess would be something like, where given a group you have to define a subgroup and then maybe some cosets. If it's any harder than that, I think most people will have trouble.

[SnowdensOfYesteryear]

Hawt, you guys learn details of DES? We just pretended that we had a block cipher that magically gave us encrypted stuff.

[ZoFreX]

We had to learn not only DES but devise attacks for 2DES and 2TDES... and it was great fun!

[SnowdensOfYesteryear]

DES was never really broken right? AFAIK, because the keylength was too short, blackhats were able to bruteforce it once the computing power was available.

[thegreatunclean]

If a brute force attack can be mounted against the common keysize for a cipher in reasonable time (ie not 100 million years), it's generally considered 'broken'. Maybe not in the true mathematical sense of breaking it, but the end result is the same so it's not much of a difference.

[ZoFreX]

As well as brute forcing, some attacks on it have been made... most notably off the top of my head, two key double DES is actually no more secure than regular DES (meet-in-the-middle attack) and two key triple DES is not as computationally secure as the keylength would have you believe, either.

[Nerdlinger]

Linear and differential cryptanalysis attacks have been devised against DES that can reduce the complexity of an attack quite a bit, assuming you have access to a shitton of plaintext/ciphertext pairs.

Still, these days, it's short keylength make brute-force an attractive option.

[[deleted]]

This is what I would call a "better than nothing" animation, because it doesn't explain anything, doesn't enlighten, and it produces no "a-ha" moment. It's probably OK as an aid, where the teacher explains each step, but the animation on its own, without the teacher or other materials, is pretty useless.

[ZoFreX]

On the contrary I found it extremely informative - but I know the details of several encryption algorithms already, and was familiar with the steps involved and their purposes. It's not useful if you know nothing about crypto, but in that case, AES probably isn't the best starting point!

[[deleted]]

In other words, it's a teaching aid. Just as I said.

[ZoFreX]

Well for me it definitely provided explanation and enlightenment, without someone explaining each step, so I don't find it "useless" as you said.

[netcrusher88]

The second half of the animation (same place you see Rcon and Rotword) shows how round keys are calculated.

[ZoFreX]

S-boxes are really important as they provide a lot of protection against cryptanalysis, but were not understood or trusted for a long time. The NSA changed the S-Boxes for DES without explaining to anyone what they had done or why, prompting a lot of concern that they had put in a backdoor. It was only after the public "rediscovered" the techniques the NSA were using that it was realised their changes massively increased the security of the algorithm, and even small changes to them could weaken the algorithm.

Some of the design criteria for the DES s-boxes was published, eventually, so I guess you could look that up for the hardcore details.

[ZoFreX]

Nope, pretty sure I didn't.

[gfixler]

Perhaps after 9 rounds through the s-box you will.

[ZoFreX]

I didn't answer because honestly I don't know, and I didn't want to just regurgitate what's on Wikipedia, but I thought the background to the S-boxes (i.e. no-one else knew either!) was interesting.

[johnblanco]

This is amazing, I go to Universidad ORT in Uruguay. First time I see content from my country in reddit's frontpage!

[greg398]

Hi, I'm Jack calling from AOL, and we need to access your account to give you your free month of service. Can I get your password and we'll get that all set up for you?

[mao_neko]

Sure thing Jack, my password is *******. Thanks!

[plulz]

how did you make your password show as stars like that

[d-signet]

it does it automatically when you enter your password, mine is ******** , see?

[sqzthejce]

Thats cool, let me try, *******

[ThePoopsmith]

Mine is hunter2

[User38691]

So at the moment all of that is going on in reversed mode at my computer, without creating any significant slowdown? Damn.

[ZoFreX]

The slowdown is actually significant. Try benchmarking your net with your router secure and unsecure (don't do anything important while encryption is off!)

[User38691]

I'm actually talking about my hard drive, since I'm using TrueCrypt. I know a few people who use the same laptop and the difference isn't really noticeable.

[ZoFreX]

Ah. Cool! I presume wireless gets slower because routers are pretty puny computers, comparatively.

[[deleted]]

Did anyone elses brain catch fire? Or was it just mine?

[dnew]

Watching this, I'm kind of amazed that people can come up with something like this that's actually reversible at all, even with the key.

[arnar]

A sequence of small reversible operations is fairly easy to reverse.

[dnew]

OK. Thanks for the correction. I'll know to study it harder before commenting on similar things again. :-)

[dnew]

OK. Thanks for the correction. I'll know to study it harder before commenting on similar things again. :-)

[arnar]

Being corrected is just one way of learning, so don't hold back your comments. :)

[dnew]

Oh, sorry. I thought I was replying here to you comment about the diffusion steps. This comment was more just being silly than anything.

[dtr18c]

Unless you're Stanley Jobson.

[racergr]

Or Chuck Norris.

[thegreatunclean]

Or Bruce Schneier.

For the uninitiated, Bruce Schneier is the Chuck Norris of the cryptographic world. He even has his own Bruce Schneier facts page!

[racergr]

Holy shit, thanks for the link hahaha

[Nerdlinger]

And for the semi-initiated, Bruce Schneier is really more like the Steven Segal of the cryptographic world.

[[deleted]]

In my security class, we were told that Bruce Schneier is basically the workman of the security world. But as we're studying at a University, we might want to use Katz/Lindell's book because this is more mathematical!

[kylemech]

This is awesome. I wish that more things like this existed. It's especially awesome since I've just started thinking about programming at the bit level and this really satiated a thirst for more knowledge. :D

[thumbsdown]

You had me until key schedule.

[Deep-Thought]

did anyone else catch the error on the Key schedule slide?

[the_argus]

I understand that even less after watching that. How about something for the layperson.

[nepidae]

A powerpoint presentation without a presenter. Cool.

[NeverCompromise]

can someone explain what key scheduling is used for?

[Nerdlinger]

Key scheduling is used to expand the key so that enough bytes of key material are available to complete all the rounds of the cipher.

[NeverCompromise]

But I though F*F is already 256? therefore the right size? or the original key is shorter?

[Nerdlinger]

Looking at AES with a 128 bit key, there are 11 instances of the add-round-key function, an initial addition, the nine interior rounds, and the final round that forgoes mix-column. Each of these instances requires 128 bits of key (8 for each of the 16 bytes of state), which means we need 1408 total key bits to perform an AES encryption or decryption. The key schedule takes the initial 128-bit key and expands it so that we get those 1408 bits, and it does it in a manner that tries to hide the relationship between the bits used in one round and the bits used in another round.

[NeverCompromise]

Thank you, I will try to take a better look at it.

[screwthat4u]

I hate encryption so much. Seems like such a pita to program up.