From 0 to cryptography | Hacker News Reader

From 0 to cryptography

techblog.rosedu.org

87 pointsmariuz39 comments

Note that unlike what TFA claims, symmetric keys are safe. They're, in fact, SAFER than public key crypto for the SAME key size, as public key crypto depends on prime numbers. That's why you'd see 256bit symmetric keys, and 2048bit or more public/secret keys.

It's just that the key exchange for symmetric keys is inherently unsafe online. But if you share the keys in a safe manner (ie, physically, secret location, no camera, etc.), its all good.

A long time ago, well, not so long in fact, before public key cryptography was invented, symmetric crypto was used by businesses. They had people carrying those keys and delivering them. That was a pain.

it also worked that way for a couple of thousand years, with weaker algorithms, but the same concept.

It's just that the key exchange for symmetric keys is inherently unsafe online.

I don't understand what you mean. There are plenty of ways to exchange symmetric keys online, for instance by Diffie-Hellman scheme, or even using public key cryptography. I even recall that SSL/TLS uses symmetric key for encryption and asymmetric crypto is used only for key exchange.

Diffie-Hellman is fine if there is no one between you and Alice, otherwise if you read the protocol you will see it is easy for Eve to do the protocol with both ends and just act as a conduit for messages after reading/altering them.

SSL/TLS relies on trusting a number of certificate authorities to verify that, yes, the other end is Bob. Note that for this to work securely you must already have their public key info. There are problems with this also but it's the best we have got right now.

There's the interlock protocol that ensures that you'll only be talking with one other party instead of one other and one in the middle but still you don't know who you're talking to.

But it's impossible to identify someone out of nowhere. Even in physical life we need external information of a person or an organization we don't know to identify him.

So, we will always need some leads with which to cross-check the other party's identity. And given that, there are plenty of protocols to exchange symmetric keys securely.

But that's exactly the problem, that there is no way to securely verify over an insecure connection that the keys you've associated with A are actually A's keys.

That's really a non-problem since how could you ever know?

The only way to verify that A's keys are legit is to use a secure channel first. Then you can leverage that over any number of insecure channels later to reconnect with A.

In the end, security all comes down to trust. It is rather hard to get 100% trust without establishing it outside the system (PGP key exchange, SSL/TLS certificate authorities).

> That's why you'd see 256bit symmetric keys, and 2048bit or more public/secret keys.

This is true for RSA based schemes, but keep in mind that elliptic curve based asymmetric schemes are believed to be secure even with much shorter key lengths.

You also need to understand whether it is safe to reuse the keys and under what conditions that is safe. Information may leak if there are repeated patterns.

Things can also be problematic if there are conditions under which you will encrypt data provided by you adversary as they could trick you into decoding the message for them.

Finally opponents may be able to tamper with the message even if they can't decode it unless there is a MAC to protect it.

This fun puzzle illustrates some of the ideas: Bob wants to send Alice something valuable in the mail. Unfortunately the postal system is very corrupt and very efficient. Any package containing a valuable item will always be spotted by postal workers. If the package doesn't have a lock the postal workers will steal the item. Also postal workers will always spot any key sent through the mail and hold it indefinitely. So even if a locked box is sent through and Alice receives it she will never receive the key when it comes through hence she can't obtain the package contents. How can Bob successfully deliver a valuable item to Alice?

Answer: Bob puts the item in a box with a lock and sends to Alice. Alice receives the box, places her lock on it and sends it back to Bob. Bob removes his lock and sends the box back to Alice. Now Alice removes her lock and obtains the package contents.

What you have described is more or less Diffie-Hellman. Unfortunately this alone wont guarantee your package's safe passage. If it did Verisign, would be out of a job.

The flaw is, you can basically just have the same scenario but replace Alice with the post office:

Bob puts the item in a box with a lock and sends to Alice. Post office intercepts the box, places their lock on it and sends it back to Bob. Bob removes his lock and sends the box back to Alice. Now the post office removes their lock and obtains the package contents.

The only way around this is to have some truly trusted third party. Even in RSA, if you aren't absolutely certain of the other user's public key, it won't work, which is why web-of-trust and other techniques are used.

Don't mean to be a shill for Coursera, but if you enjoyed this article you might like Coursera's crypto class: https://www.coursera.org/course/crypto I found it really challenging in some places, but also quite fun.

Udacity also has a crypto course: http://www.udacity.com/overview/Course/cs387/CourseRev/apr20... I haven't tried it yet, but it looks a bit more in-depth in some places than the Coursera course.

If you read this and intend to make security design decisions based on it (as opposed to reading it just for fun), please read more about the subject from other sources as well. A few statements in it are a bit contradictory, like claiming DH is safe from MITM while at the same time in other words acknowledging e.g. that identity cannot be proven with it. I don't mean to bash the author as primers are a good way to get people interested in stuff, but small oversights can sometimes cause big problems.

And before you tackle those other sources, make sure to go on a week-long bender. This will hopefully kill enough brain cells that you might stand a chance of forgetting most of this post's mischaracterizations.

I can condone running through the math behind various primitives, to wet someone's whistle and give them a bit of an appreciation. To someone unfamiliar with the concept of one-way functions, seeing a run through of Diffie-Hellman is pretty neat. "What do you mean I can't figure out the secret, the numbers are right here in front of me..."

But one of the major things that makes crypto so damn hard is that the devil is in the details, and this article misleads much more than it informs. Linear analogies like paint-mixing and XOR (!?) are anti-enlightening to the feat that DH actually accomplishes. Never mind the blatantly incorrect summaries of the properties of each primitive, which were clearly driven more by the limited understanding of the author than any kind of real-world usage.

If you thought this link was useful, I'd be interested in knowing why.

I'm interested in knowing why your post implies that its not useful. I would like to know if its worth reading as I've just added it to Read It Later.

EDIT: Please correct me if you didn't mean to come across that way, it's just the last comment on the blog:

> this post is just terrible. i don't understand why people feel the need to learn a tiny bit about a subject, and regurgitate their misunderstandings through blogging. please take it down, you are making the world a worse place.

has made me wary.

I'm asking seriously, not just to make a point.

Not sure what your problem is with the article, it's a basic intro article. Clearly the people that find it useful are the people who do not know the material and don't need to deal with this on a regular basis.

So I'm curious what you do with a basic understanding of, say, the RSA math.

Some things are worth knowing just out of curiosity. I always found the RSA algorithm fascinating in its own right, despite the fact I have no intention of ever implementing it myself. I'm not a mathematician nor a computer scientist, but I find an appreciation of certain algorithms not unlike the appreciation of art. Pointless in a pragmatic sense, but intellectually satisfying.

I can't speak for this article specifically though; I think there are better explanations out there, not to say that this one is bad. It is a difficult topic to explain after all, especially when you don't know the level of math background your audience has.

Realize the number theory is not useless and continue studying it.

What do you do with a basic understanding of limited-slip differentials, frequency modulation, the Maillard reaction, or any other number of subjects? If you're anything like me, what you do is take joy in understanding a little more about how stuff works, however superficially. And who knows when some grain of knowledge could be a useful inspiration in some seemingly unrelated area where you do have expertise? That happens more often than one might think, especially with mathematics.

I get that you worry some well-meaning fool will read this and go implement their own botched RSA-based or DH-based cryptosystem. That concern is legitimate. By all means, post the customary warnings.

Right - I think it's part of the mindset of the hacker to assign intrinsic value to a basic understanding of how things work. From the Krebs Cycle to the lifecycle of a star, it's all interesting.

I personally love studying and thinking about Fully Homomorphic Encryption. It has the potential to revolutionize the world similar in flavor to the discovery of Public Key Encryption. In short: it allows you to perform computation on encrypted data. In other words, all programs are data, and now you can perform computation on encrypted data, so now it's impossible for anyone but the encryptor to know what computation is being done. It "hides the intent" of algorithms, just like Truecrypt hides the facts sitting in your passwords.txt file.

The implications of this are enormous and a ton of fun to think about. Here's just one example of how the world might change: there's a nonzero chance that in less than a century most computer programs will be fundamentally impossible to reverse-engineer. The old metaphor "you can think of a program as a black box; input goes in, results come out" will become a law of nature, rather than a mere rule of thumb. Now add the fact that the output will probably be encrypted using today's techniques, and the result is striking: any program running on your computer will be free to vaccuum up any data it pleases, encrypt it, then surreptitiously transmit it to its owner. It will be impossible to know ahead of time whether any given program is malicious; the sole way of detecting maliciousness is reduced to (a) the program is reading files that it normally shouldn't be, like your browser history, and (b) a secure HTTP connection is active. So if you give your program a legitimate excuse for (b), such as "my program is a web browser, go ahead and use it" and a legitimate excuse for (a), such as "obviously my browser is going to read and write your history file", then suddenly you wind up in a situation where the browser could be secretly sending your entire history to some third party and it'll be fundamentally impossible for you to detect it's happening.

FHE exists. It is coming; Gentry's thesis proved it can be done. The current problem is that the computational cost is probibitive (e.g. If we say that "right now the cost of computing a+b is N", then using Gentry's FHE the cost would be N^6, if I remember correctly; and that's true for every operation, so sub, mul, etc become N^6 more costly to compute) but work is underway to reduce that cost to something more palatable.

This is, of course, completely useless to me and to my life. Working on this is unlikely to gain me any useful knowledge nor any applicable talent/experience. By extension, no economic value can be derived from this right now (probably not within our lifetime). So who cares about it? Well, the answer is obvious: few-to-no one. I just have fun doing it because I can; it makes me feel powerful that I can understand and apply this sort of knowledge a century before it becomes commonplace.

So why have I been babbling about all of this? Well, I just wanted to thank you, because about 6 months ago you posted a comment along the lines of "the Diffie-Hellman protocol is actually pretty easy to understand", so I nonchalantly checked it out. It was amazing, and led me to devour a bunch of texts on RSA etc (leading to an understanding/appreciation of the RSA math) and eventually branching off into my current explorations of the mysterious world implied by FHE. And "Diffie-Hellman -> RSA -> scrypt -> FHE" just happened to be my path, which just happened to be "useless" (in the "hey I need to make rent" sense) but some other person might have easily gone "Diffie-Hellman -> RSA -> studying OpenSSL -> an ability to send and receive information in a way that's fundamentally impervious to any known attack (otherwise it would be fixed already, since the whole world uses OpenSSL) -> setting up a remote, untraceable C&C server for your Lua-based virus (a.k.a. Flame) -> influencing world events", which is presumably much more useful.

So the answer to the underlying question of "why do this type of thing?" can, I think, be expressed roughly as "meh, it's either fun or useful depending on what kind of person you are and your goals, and by the way thanks for originally encouraging me to look into it."

Do you have the link to this article still? I would love to take a look at it.

What's WRONG with it?

> When disagreeing, please reply to the argument instead of calling names.

You're implying the article is useless, and that it shouldn't be here. Justify that, if you're going to go through the trouble of making a post.

I'm asking a question. Did you think the article was useful? I'm interested in why.

Now I'm interested in why you're interested in knowing why people thought the link was useful.

If you have an opinion about the post in question, why not just state it?

Although I initially thought it was meant as an insult towards the beginner nature of the article... taking a look at Tptacek's profile would lead me to believe he is interested in meeting people with skill and interest in security and encryption, maybe for employment purposes. Don't leave us hanging, am I right?!

Remember this?

http://vimeo.com/9260794

Somehow found myself watching it a few weeks ago. In it the biggest realisation I had was that I would have been just as likely as the developers at flickr, vimeo etc at punching in `sha1(secret_key + 'foobarbarbaz')` for computing a MAC. Thus began my foray into cryptography. My reading list is a little backlogged but 'Cryptography Engineering' is bubbling its way to the top.

My biggest takeaway so far is to just stay the hell away from crypto, but I work with other developers on big codebases, so I need the knowledge firepower to convince them to stay the hell away from crypto.

That being the case, there wasn't much I wasn't familiar with in the article, but since I'm a crypto newbie it was nice to go over those concepts again.

This article, I'm not such a fan of because it's poorly written and doesn't really cover much.

In general, I'm a fan of having the average developer know something, and in general I want that "something" to be:

1. Here's some basics on how crypto works

2. Here's some basics on how it gets broken

3. Here's how you can screw up even with well-designed systems

4. Here are some solid things that will see you through if you use them correctly (plus how to use them correctly)

This article doesn't really do any of that.

I found that to be a pretty nice writeup, a little more accessible for the curious layman than a pair of blog entries I wrote on RSA (http://cautery.blogspot.com/2012/06/rsa-encryption-and-other...) and Elgamal (http://cautery.blogspot.com/2012/07/encryption-part-2-elgama...)

Encryption topics were the big wake-up call for me regarding not relying on Wikipedia for math/tech info. When I started the above blog posts, I dug around for background info from a variety of sources until I got my head around the math, and found Wikipedia's entries on encryption topics to be basically unfixable without doing a large enough rewrite to guarantee an immediate revert.

Anyway, I wish this rosedu post had come a few months earlier; it would have saved me quite a wild goose chase.

Great Link, thank you.

Site down?

http://rosedu.github.com/techblog/from-0-to-cryptography.htm... , perhaps!

http://techblog.rosedu.org/from-0-to-cryptography.html

Reply on news.ycombinator.com