sdevlin

I think it would be tough to attack TLS with this.

A couple important stumbling blocks off the top of my head:

We need to pull off the attack in the context of a single TLS session, because new AES keys are generated for each one. This means we can't choose any inputs to the AES function. If we try to manipulate or forge a message, the MAC will fail and then the jig is up. This might not be a big deal, since the AES ciphertexts will seem random anyway.

There will be a large amount of overhead in each request compared to Bernstein's original experiment. This will likely introduce a large amount of per-request jitter. With enough requests we can iron this out, but again: one session. So there may be an upper limit on the number of samples we can realistically take.

We may have a tough time comparing like to like. Certainly we can request the same static resource each time if we control malicious JavaScript, but there may be confounding factors. This might not be a big deal, since I think this just amounts to more jitter.

This attack is conceptually simple, and the linked paper (http://cr.yp.to/antiforgery/cachetiming-20050414.pdf) is very approachable for the layman. I recommend giving it a read.

Here's the basic idea:

  1. The first thing the AES encrypt function does is XOR user input against the secret key.
  2. The result of this operation is used to index into a lookup table (the S-box).
  3. The timing characteristics of step 2 will vary based on the contents of the cache.

By measuring the timings for a large number of random inputs and correlating them by index, (e.g. sort all messages into buckets based on the value of the first byte), we can recover the corresponding byte of the secret key.

Though it's not clear a priori what the timing characteristics should look like for a particular key byte, we can easily measure this on a machine we control that matches the description of the target platform.

One of the requirements for the attack is partial plaintext control. This is feasible if you're running malicious JavaScript in the user's browser.

So what you do is generate an HTTP request that, taken together with the SSL MAC, will align on a block boundary. Then you're guaranteed to have one full block of padding.

It might sound difficult to pull this off with multiple unknowns (other cookies, user agent string, etc.), but in practice it would be easy. You could make sure things line up correctly just by incrementing your packet length by one byte at a time until you see the record size jump by a block.

What are dynamic modules?

In duckduckgo you can just do:

    [query] !pb

Pinboard is an awesome service. If you don't have an account, you should. It's especially refreshing for those (like me) who despise the Internet of JavaScript Bullshit. Pinboard is fast as hell because it doesn't waste your time with flashy nonsense.

Second: Maciej is a great writer. If you're not reading his articles (http://www.idlewords.com/), you should be.

> If you split into multiple parts, each part of the key is useful: it lets you reduce your search space by however many bits of the key you have.

That doesn't have to be true. Rather than splitting an AES key K into substrings, a better approach is to choose n parts such that:

    K_1 ^ K_2 ^ ... ^ K_n = K

None of the component K_i will reveal any information about K without knowledge of its peer components.

Those connections needn't be concurrent.

> You need 16 million connections with 1GB of data, _in_ _each_ _connection_ to practically attack RC4.

This isn't accurate.

There are two major attacks described in the recent literature on RC4.

The first targets single-byte biases in RC4. Simply: the distribution of key stream bytes at a given index is biased across all keys. By collecting a large number of ciphertext samples, you can match the bias in the ciphertext to the known biases in the key stream to recover plaintext.

These biases are only significant early in the key stream, say the first 256 bytes or so. Because they're only prevalent early in the key stream, you need to make a lot of connections.

This attack isn't a great fit if your target is a user's HTTP session, for two reasons. One is that you need to make a ton of connections, and there's not (to my knowledge) an easy way to force that from the attacker's perspective. Even if there were, you would incur quite a bit of overhead from all the TLS handshakes. The second and more important reason is that the HTTP session cookie just isn't going to show up in those first 256 bytes.

The second attack targets double-byte biases in the RC4 key stream. Again, these biases are known and measurable across all keys. By collecting a large number of ciphertext samples, you can perform analysis to recover plaintext. This is a little more complex because there is interdependence between bytes, but still not so tough. (Search for "hidden markov model" and "viterbi algorithm".)

The double-byte biases show up at regular intervals over any given key stream. This is important! It means the number of connections is irrelevant to plaintext recovery. What matters is just the amount of ciphertext you can collect.

This makes it a much better choice to attack HTTPS. We can collect all the ciphertext we need from one TLS session (or three or four or five, it doesn't matter). And we can also exert much finer control over where the HTTP cookies show up. As an attacker running JavaScript in a user's browser, you have this ability.

As the research notes, neither of the outlined attacks is practical today. But they're both knocking on the door. What if higher bandwidth or browser changes allow an attacker to take samples more quickly? What if someone refines the algorithms outlined in the paper? To the latter question, there are additional multi-byte biases (Mantin, 2005) they don't account for in their attack. It doesn't seem far-fetched to suppose these attacks could be improved.

So, is RC4 a game-over vulnerability in the context of TLS? Of course not. But conscientious site operators should look to migrate away from it as soon as practicality allows.

Advanced search often leads to SQL injection. This is because there are some parts of SQL queries that can't be parameterized. If you allow the user to dynamically select which table to query against, or which columns to fetch, or how to sort or group the results, you need to sanitize all of these inputs by hand.

This is why saying "it's easy, just parameterize your queries" is bad advice. It's incomplete. There are still these unfortunate holes in most stacks that require you to be careful and whitelist user inputs.

None of that requires JavaScript. You basically just described the Lavabit model, where user passwords were used to derive key material that was never stored on the server. If you trust the server to give you good client-side code barring exceptional cases, you might as well trust them to discard your password after use.

Just to be clear, are you suggesting that there is an elite cadre of cryptobullies browbeating the general public into broadcasting compromising information all over the cleartext internet?

Burp Suite has a pretty rich feature set. How does this compare? For example, is something scriptable like Burp Intruder included (or planned)?

Conventions and usage vary by setting, but yes, it's to prevent nonce reuse.

A typical scenario might use a single encryption key for many different messages. A simple strategy is to allocate 64 bits to a message counter and 64 bits to a block counter. For each encryption you can increment the message counter by one. The block counter starts at zero and increments for each block of the message.

Note that this imposes hard limits on both the number of encryptions you can perform with this key (2^64) and the number of blocks a message can contain (also 2^64). As long as we respect these limits, we're guaranteed never to reuse a nonce.

If we use a random 64-bit nonce in place of the message counter, the picture changes a little. Due to the birthday paradox, we can now expect a collision in around 2^32 encryptions, which is a little close for comfort.

Fortunately, we can tune the bit allocations based on the needs of the application. So a reasonable strategy might be to bump the random message nonce to (say) 96 bits and leave 32 for the block counter. This still allows individual messages of around 64GB.

Of course, parameters like these should be considered implementation details for 99% of application developers. The best thing to do is to use a high-level library like NaCl that makes reasonable choices and then abstracts them away.

That would not solve the problem of active man-in-the-middle attacks.

It seems pretty trivial to me. Can't you just send different messages to different people?

> For example, Alice can tell Bob "The funds were transferred, thanks!" and tell Carol "Bob is stealing money." — and the protocol will ascribe integrity to the messages for both participants and label them as the same message.

Isn't this trivially possible in Cryptocat for anyone who controls the server?

Here's one possible approach.

Assume the attacker can modify plaintext on disk indirectly. This might be viable if e.g. the user's browser cache lives in the TC volume. (Not sure what typical TC-in-Dropbox usage patterns are, so this may or may not be realistic.)

Further assume that the attacker can observe ciphertext changes in Dropbox.

XTS is vulnerable to the same byte-at-a-time plaintext recovery attacks as ECB. This is usually irrelevant, because adaptive chosen plaintext attacks are outside the threat model considered for FDE. But in our scenario, the attacker has at least some degree of plaintext control.

The success of this attack will depend a lot on how fine-grained the attacker's control over his insertion point is, i.e. can he reliably write to the same location over and over again? Any number of components might thwart that control, so I'm not sure how easy it will be to make this work.

Thanks for the great reply!

I didn't realize the Chrome web store requires your private key. That's insane.

> The best way is a browser extension, but even that has its pitfalls (firefox especially since there's no real sandboxing).

I would be greatly interested if you could expand on some of the pitfalls of browser extensions and how they differ among browsers. Thanks in advance!

That is a pretty good list of recommendations, but I have a couple criticisms.

The recommendations are mostly low-level. None of them are wrong, but they put undue burden on developers to get details right. For example, the AES-CTR recommendation doesn't talk about nonce management, but this is critical to the security of the construction. Application developers should always use the highest-level cryptographic constructions they can get away with. As such, many of these bullet points could be replaced with a recommendation to use PGP or NaCl.

Also, the list skimps on random number recommendations. It talks a bit about how big numbers should be, but it doesn't discuss sources. This is really important as RNG is a weak point in many systems. Short answer: use /dev/urandom.

The web is not a secure medium for this kind of application.*

This is because all the encryption features they tout depend implicitly on content (HTML and JavaScript) the server sends you every time you use the application. Because you receive this content anew on every usage, there's no way to verify what you're getting. Today it might be fine, but tomorrow it might contain a key logger or subtle cryptographic flaws.

You also can't depend on the community for help verifying this content, because it can be distributed selectively. The mass of users might get benign content while interesting targets get backdoored software.

* It might be safe to distribute something like this as an installable sandboxed web application. I'm actually not 100% certain. But the no-install-just-browse-to-this-url model is definitely insecure.

Simply: performing a timing attack against a hash function implies performing a second-preimage attack against the hash function.

That is a good way to think of it. Indeed, that is how cryptographic randomness is typically defined.

Simply put: given the first k bits of a random stream, can you predict the k+1th bit (more than 50% of the time)?

A generator that passes this test will pass any statistical randomness test, but the converse is not necessarily true. For example Mersenne Twister is a good generator from a statistical perspective, but it's actually quite easy to recover its internal state by observing a small amount of output. (Around 20k bits, if I recall correctly.)

Python has a decimal package in stdlib. It provides an arbitrary-precision floating point type. The performance will obviously be worse than with floats, but I doubt it matters in an intro programming class. The only real drawback is that there are no decimal literals.

Actually, several languages I know of have decimal types in stdlib. Two that do not are C and JavaScript.

Then what's the point?

> "Nobody is going to die."

This isn't accurate, e.g. http://cryptome.org/2012/07/chile-comments.htm .

Bad crypto is actually much more dangerous than a single rogue dentist.

> However, it is not a matter of debate that the RSA backdoor of BSAFE was and is not open merely to the NSA. It is an objective fact that anyone can take advantage of a backdoor like this.

This is not accurate. You need to know the private key for the generator, and this is not publicly known.

That's an old-school C function declaration. Note that the function return type are parameter types are implicitly int. nE is then explicitly declared to be a char pointer pointer.

More importantly, all encryption keys are either fixed or stored directly alongside ciphertext.

The cryptography in this system seems to be 100% cosmetic, so I'm not sure things like ECB mode or absence of MAC really matter.

EDITED for clarity.