"Cryptography isn't something you can iterate on until you get it right, because you'll never know if you do."

People who try the iterated design approach are especially frustrating. It ends up becoming a game of whack-a-mole with vulnerabilities, wherein an experienced cryptanalyst will point out an issue, the designer will say "oh! of course! let me apply a patch!", and then this continues to infinity. (This scenario doesn't necessarily indicate a bad approach, but it's certainly a symptom of iterated design.)

There's a particularly lovely story in Schneier's "Memo to the Amateur Cipher Designer" [1]:

> A cryptographer friend tells the story of an amateur who kept bothering him with the cipher he invented. The cryptographer would break the cipher, the amateur would make a change to "fix" it, and the cryptographer would break it again. This exchange went on a few times until the cryptographer became fed up. When the amateur visited him to hear what the cryptographer thought, the cryptographer put three envelopes face down on the table. "In each of these envelopes is an attack against your cipher. Take one and read it. Don't come back until you've discovered the other two attacks." The amateur was never heard from again.

Part of what makes it so frustrating, though, is that usually we want to be genuinely helpful. Building cryptosystems is fun (dangerously so!), and it's really crappy to end up saying "just scrap the whole thing" or what have you. But if you want to keep your sanity...

[1] https://www.schneier.com/crypto-gram-9810.html#cipherdesign

http://www.matasano.com/articles/crypto-challenges/

Myself, I'm trying them in ANSI C

Its OK to let them use it so you can have a large user-base to test with, you just need to explain to them that it isn't proven secure. As in, explicitly tell them that they are under no circumstances to use it with sensitive information.

Playing around with cryptography is the only way to learn it, you just have to remember to tell people that playing is exactly what you are doing.

First, while "playing around with cryptography" may be the only way to learn it, building cryptographic systems is just about the worst way to learn. Professional cryptographers start by cryptanalyzing targets and use that experience to inform their future designs. On the other hand, veteran implementors who have never taken the time to learn how to break crypto turn out protocols and designs that are repeatedly broken. You can see that right now with TLS and the TLS working group, which still hasn't fixed MtE block ciphersuites because veteran implementors can't get it through their heads that MtE is a design flaw.

Don't learn by building. You need to learn by breaking.

Second, more than one project has done the tightrope walk of telling their users "this isn't really safe" but then misleading (innocently or not) non-savvy users into trusting them. One project made it clear that their system wasn't "ready" to defend against nation-state adversaries... but then suggested that maybe it would be good enough for journalists, and even promoted it at an event for teaching journalists cryptography. It was later comically broken.

Be honest with yourself. Crypto doesn't get beta-tested into resiliency. Strong systems start out strong. If you're building something because its your dream to thwart the NSA, don't kid yourself into thinking that you'll get there by first protecting people's Warcraft clans.

The best way to do this is to do the Matasano crypto challenges. The challenges are designed to get progressively more difficult, and since the goal of most of them is to break something, that means you'll learn how to employ progressively more sophisticated attacks. They're also great for a newbie, because in one challenge you'll implement something that seems impervious to attack, then in the following challenge you'll attack and break it, often via an unexpected attack vector. (The padding oracle attack comes to mind.)

You'll come away with an understanding of AES in ECB CBC and CTR modes; HMAC; timing attacks; attacks on RNGs; attacks on hashes; and a lot more. That's just off the top of my head.

For me, there were a dozen "aha!" moments in the first 30 challenges. Each of those moments now live with me and inform my future decisions. They will also make you much less confident in your ability to design secure cryptosystems, which is good.

Can't get it through their heads that MtE is a design flaw? You're more generous than I would be. At this point I'd assume that everybody knows that MtE is a design flaw, and anyone designing a protocol which uses MtE has made a deliberate decision to design a weak protocol.

Maybe the process is just counterintuitive, but it seems that no matter how skilled someone might be at breaking systems, that building a sound system on the first try would still be incredibly difficult. I know that crypto systems aren't built iteratively, instead I'm talking about going back to the drawing board each time. Would there be value in that, or would it be a waste of time? I'm not yet an expert (and I am well aware that you are), though I aspire to be one day. Perhaps you would be kind enough to elaborate?

Both and neither. Once you get really good at breaking cryptosystems, designing them looks very similar. You start with best practices: use sane primitives (or thoroughly vetted components, preferably!) and put them together in known, simple (simple is key) ways. Then you put on your breaking hat and you attempt to violate every constraint. If you find a flaw, then you iterate or redesign. Once you are happy with it, you start showing it to other crypto breakers, until they're happy with it too.

At this point, you have something that would withstand most basic attacks, and you might be ready to put it out into the world. It's still not battle-hardened and ready for uberconfidential data, but it's in a better state than most cryptosystems. As more and more people look at it without owning it, its trustworthiness goes up, and the risk goes down.

Secure cryptosystems don't pop out of nothing; they're iterative, but not in the "I should do a Show HN" sense. It's iterative like writing a poem -- you don't release it one line at a time.

I can also learn by reading standard and read how people implement in projects like Firefox or Chromium. And ask questions. I think we should be careful with the meaning of "learn by breaking" because obviously only a handful of people can really break cryto system. And average developers like me are probably better off just learn and break.

Steps like that are probably my way of getting into security engineering and cryto engineering (at some point). I guess I am a different audience, I am not here to break RSA, I am here to learn how real systems are implementing RSA, TLS and see whether those implementations have flaws or not.

Perhaps the general population won't be interested, but techies are often willing to play around with unproven technologies.

We'll be using this text:

http://www.amazon.com/Introduction-Cryptography-Coding-Theor...

Is this any good? Apparently a best seller in the "Software Coding Theory" category on Amazon.

The book does very good job of talking about different algorithms and concepts, often times with a very brief historical introduction, and includes thorough descriptions of various popular/important attacks of those concepts. In general it's a book I'd recommend for an introduction to cryptography. You also learn a fair introductory bit of number theory which I really enjoyed.

I also met Dr. Washington, one of the co-authors of this book, who was a very pleasant and energetic person who really enjoys the topic of cryptography.

By the way, where are you taking this course?

I'm taking this at Millersville University as a once-a-week, 3 hour evening course. I'm a Physics and CS major, and am taking it as an elective to get a Math minor.

With all the NSA and crypto news these days, it sounds like a great time to learn about the fundamentals of crypto. And I'm curious if there will be actual programming involved because to my knowledge, there aren't any prereqs for it, not even an intro to programming course.

Although I thoroughly enjoyed the Mathematical focus of the course, my particular teacher spent a good deal of the course discussing semi-related Number Theory topics at the expense of introducing some of the more interesting cryptography concepts. That said, we still learned the theory behind the important ones: DES, AES, RSA, and ElGamal, in addition to "classical" forms such as Caesar, Vigenère, and Hill.

Another downside of the course being a Math course and not a CS course: we used Mathematica for all of our "programming" projects, which felt awkward and clunky. I remember coding my solutions in Python first, making sure they were correct, and then translating them to Mathematica after the fact.

Good luck in the course! It'll be hard work, but its absolutely worth the effort.

That concern is reflected in the textbook and his course. It's a very approachable treatment and it seems like a lot of emphasis is placed on making it fun.

The downside to a math listed CS crypto course (as it is where Washington teaches) is that there may be less emphasis on flaws that occur in actual real word implementations. A professor in the CS department also teaches crypto at Maryland and actually uses a different book (one he wrote). My understanding is that there is a bit more attention paid to implementation there, but that's coming second-hand.

for all you conspiracists - this was designed by rivest, the r in rsa, now famous for cooperating with nsa... (i don't really believe that the permutation is a backdoor, but i would like to know how it's derived - rivest is famous for elegant algorithms, and for the life of me i can't find a simple, neat way to get those numbers from pi)

https://www.rfc-editor.org/rfc/rfc6149.txt

Do you believe that the starting state for MD2 is a possible backdoor?

Later: I'm batting .000 today on this stuff; it's not the starting state of MD2 that he's talking about, of course, and the misapprehension that he was is part of why I was dismissive. Go me.

However I strongly doubt this is one. The attacks that have broken MD2 do not seem to hinge terribly on the Sbox (I may be wrong, it was only a cursory look). It's more likely to me that the Sbox was generated using a hard-to-replicate Knuth shuffle using the digits of Pi.

how would you derive it? tagging pairs of hex digits and sorting doesn't cut it. would rivest have used a hack that's a biased shuffle? i doubt it.

and downvotes. happy xmas!

also, did you see http://www.jakoblell.com/blog/2013/12/22/practical-malleabil... which i think could be added to an early crypto challenge? (but maybe you already cover the idea).

This was interesting for me to think about because it seems like a counterpoint to the article, in that it is a very successful project that came about in a very "quick and dirty" way as opposed to starting with formal protocol design.

--

I see that Linus disclaims the idea that SHA1 is about security: "Git uses SHA-1 in a way which has nothing at all to do with security.... It's just the best hash you can get.... It's about the ability to trust your data. I guarantee you, if you put your data in Git, you can trust the fact that five years later, after it was converted from a hard disk to a DVD to whatever new technology and you copied it, five years later you can verify that the data that you get back out is the exact same data you put in."

But it seems like avoiding attacks like this must also be a goal: http://lkml.indiana.edu/hypermail/linux/kernel/0311.0/0621.h...

The content addressable data store where all the objects are kept is basically a filesystem where every filename is the SHA1 of its contents.

If you were to generate an object that was a SHA1 collision of an existing object and inject it via a commit (without access to filesystem, otherwise the point is sort of moot) then git won't overwrite the original object with that SHA1[1].

Maybe there's some other mechanism in Git that you're referring to that uses SHA1 as a MAC that I'm perhaps unaware of?

[1]: http://stackoverflow.com/questions/9392365/how-would-git-han...

This is definitely outside of my expertise, so I'm sure that my understanding is incomplete. The larger questions for me are:

- if git's SHA1 content-addressable design is not crypto, how do you distinguish crypto from software like git that uses cryptographic primitives for useful purposes?

- is a project like git a safe/sane thing for a non-cryptographer to design and implement? If so, why do all the warnings in this article not apply?

It happens to be a hash with fairly good collision resistance. Maybe not the best we have for modern crypto purposes, but that's not what it's being used for. It's being used to check and record unique tags for patches (as far as I know, my git knowledge is far from complete).

Cryptography does concern itself with data integrity but the reverse does not have to be true if you're not talking about part of a system you care about mitigating attacks on.

That's my take anyway.

--Edit-- for completeness I should add that SHA1 by itself is absolutely not a MAC

In as much as SHA1 is a "cryptographic hash function", Linus isn't taking advantage of a few of it's cryptographic properties in his usage of it in git. It would for example, make no difference to the workings of git if you could reverse-engineer the contents of an object from its SHA1. In the same way, it doesn't matter much to the operation of git that you can generate collisions for SHA1, though if you were running into collisions all the time, it would make everyday usage difficult.

> if git's SHA1 content-addressable design is not crypto, how do you distinguish crypto from software like git that uses cryptographic primitives for useful purposes?

If I'm understanding you correctly, software that "uses cryptographic primitives for useful purposes" is usually trying to guarantee one or more of the following:

* Confidentiality - Keeping data secret

* Integrity - Making sure data hasn't been tampered with

* Authentication - Making sure that the person you think sent the data is in fact the person who sent the data.

* Non-repudiation - Ensuring that the person who sent the data can't deny that they in fact sent the data.

Git makes guarantees about none of the above in its usage of SHA1. You could argue that it makes a guarantee of integrity in its content addressable file store, but it doesn't. If you can modify the files in the .git/ directory, you can screw up the repository to your hearts content. There's no way to do so remotely, i.e. by creating and pushing a Git commit with an existing SHA1. You typically protect Git from local tampering by only allowing access via SSH, which has plenty of crypto in it.

When it does make guarantees about authentication (signing tags) it uses GPG more or less off the shelf. In that case the SHA1 is a reference to a commit object, and you're saying that "I, Najaf Ali, sign off on the commit with this SHA1". It doesn't guarantee anything about the contents of that commit if the repository has been tampered with.

> is a project like git a safe/sane thing for a non-cryptographer to design and implement? If so, why do all the warnings in this article not apply?

See above on git not making the guarantees that software that "uses cryptographic primitives for useful purposes" tend to make. Since Git makes none of those guarantees, it's (I think) a safe/sane thing for a non-cryptographer to design and implement. In practice, what Linus has done has let other off-the-shelf crypto (SSH and GPG) make the required guarantees for him.

> [A signed commit] doesn't guarantee anything about the contents of that commit if the repository has been tampered with.

I think most people would intuitively expect the signed commit to guarantee the contents of the tree being signed. The idea that you could "git pull" a repo from a compromised machine, verify the signed commit, but not actually have a guarantee about the tree matching the one that was signed would run counter to most people's expectations, I suspect.

In other words, this to me seems like a "technically, we don't guarantee" statement about something that is de facto thought to be guaranteed.

I'm not sure that it says anywhere in the documentation that it guarantees anything more than that, but I agree that a significant proportion of developers would intuitively expect that the entire content of the tree to be signed rather than just the SHA1.

Further evidence that they do assume that: https://news.ycombinator.com/item?id=7003900

Attacks like mentioned can be prevented by a number of mechanisms and checks for changes. If a hash being secure helps that is great but that isn't why git uses hashes. Or by separately signing commits.

git does use crypto but reuses existing crypto (https and ssl to communicate between repos and someone mentions you can use GPG to sign commits) rather than developing it's own secure protocol.

Katz and Lindell's Introduction, on the other hand, is absolutely fantastic for the task (this was its design goal...). It introduces theoretical cryptography from the bottom-up and uses it to motivate the various primitives and constructions from the applied realm. It's really a great mix. The book has become my go-to recommendation for those who are serious about cryptography but have had relatively little exposure to it. It also doesn't assume the reader is an expert in all things computer science, which is nice.

Goldreich's Foundations of Cryptography is more of a treatise on theoretical cryptography... it goes much deeper and starts out assuming the reader is pretty familiar with concepts from theoretical computer science and probability theory. The optional sections of Katz and Lindell's work end up being the opening chapters of the first volume --- and they're not optional. Block ciphers aren't even treated until the second book. It's a seriously theoretical series, which makes it great in its own right, but I would postpone reading it until well-after Katz and Lindell's book. (And a book on computational complexity, at minimum, for those not familiar with it.)

It seems kinda superfluous to mention Applied Crypto when the real reco is to read Cryptography Engineering. I'd almost wonder if it would be better to direct people away from Applied Crypto...

Personally, I found Applied Cryptography to be so-so at best. Practical Cryptography was a breath of fresh air in comparison.

If you want to learn crypto and do crypto then certainly start with this. Then, when doing crypto...practice. Build it and reach out and ask for help and talk to people who know what they are doing and learn from them. Ask them about problems you encountered and ask them about the best ways to solve them...otherwise you will continue to make the same mistakes.

Interesting to contrast this with patio11's statement from just a few days ago (https://training.kalzumeus.com/newsletters/archive/sco_remin...):

> People are better at remembering images than they are remembering claims or facts. "256-bit SSL encryption" is a true fact about your software product, but for most customers it goes in one ear and out the other. "Bank-grade encryption" is an image -- people can envision the vault -- and is vastly more likely to be recalled favorably when someone is worried about security.

N.B. Patrick also says to use your powers for good rather than for evil :)

I have a question about MACs. We're using HMAC based on SHA256 with 32-byte keys on our new system, but our security architect only wants us to send and verify 4 or 8 bytes of the MAC output. Am I wrong to be suspicious of this? It massively reduces the number of bits an attacker has to guess or calculate, though at 8 bytes that's 128 bits so not exactly a quick brute-force...

Truncation is mentioned in RFC 2104. I quote:

5. Truncated output

   A well-known practice with message authentication codes is to
   truncate the output of the MAC and output only part of the bits
   (e.g., [MM, ANSI]).  Preneel and van Oorschot [PV] show some
   analytical advantages of truncating the output of hash-based MAC
   functions. The results in this area are not absolute as for the
   overall security advantages of truncation. It has advantages (less
   information on the hash result available to an attacker) and
   disadvantages (less bits to predict for the attacker).
   Applications of HMAC can choose to truncate the output of HMAC by
   outputting the t leftmost bits of the HMAC computation for some
   parameter t (namely, the computation is carried in the normal way
   as defined in section 2 above but the end result is truncated to t
   bits). We recommend that the output length t be not less than half
   the length of the hash output (to match the birthday attack bound)
   and not less than 80 bits (a suitable lower bound on the number of
   bits that need to be predicted by an attacker).  We propose
   denoting a realization of HMAC that uses a hash function H with t
   bits of output as HMAC-H-t. For example, HMAC-SHA1-80 denotes HMAC
   computed using the SHA-1 function and with the output truncated to
   80 bits.  (If the parameter t is not specified, e.g. HMAC-MD5, then
   it is assumed that all the bits of the hash are output.)

I know some of the older MAC techniques (ANSI X9.19) turn out to actually aid key recovery if you use shorter MACs, which is odd...

(Can't really complain though, it's excellent and free)

NaCl is very much a step in the right direction, but it's not an end-all solution either. Key management alone is a huge issue, for example, but virtually no library helps you out there beyond providing a basic toolkit. Of course, key management is very much in the realm of policy, so that's to be expected.

I have signed up to the Coursera course and hope to brush up on basic topics and start doing more advanced crypto.

Real mature.