4

In movies and TV shows, characters are often depicted using devices and applications that are able to determine an encryption key or passcode character by character (or digit by digit). I am a programmer and think I have a decent idea of how encryption works in general but I'm not sure whether to take this as a simple way to display progress or if there is actually something to it.

Is this ever possible and if so what properties of an algorithm leave it susceptible to this kind of cracking?

10

If an encryption system allows for character-per-character cracking, then it is awfully weak, and should not be used.

Mathematically, block ciphers are defined as pseudorandom permutations. A block cipher works over the space of blocks of length n bits; such a space has size 2n. There are 2n! permutations over that space (that's a factorial, meaning that the number of possible permutations is huge). A secure block cipher is such that it is indistinguishable from a permutation selected at random, uniformly, in the space of possible permutations: each key is supposed to correspond to such a random choice of permutation, and, crucially, all choices for all possible key values are independent of each other.

What this means, in mundane words, is that for a secure block cipher, either you have the whole key, exact down to the last bit, or you have nothing. Contrary to Hollywood depictions, an "almost good" key does not result in a "blurry plaintext": if even one key bit is wrong, you should get random junk (that is, an output which is sufficiently indistinguishable from random junk that you cannot know whether you are close to the right key or not).


Of course, if the encryption system is weak, anything goes. @Mark cites a case of "splitting" (in WPS) which is an atrocious weakness that can, indeed, be exploited for faster attacks. Padding oracle attacks also work over a byte-by-byte leak which allows for byte-by-byte reconstruction of the plaintext (not the key, but still).

Another, more technical example, is the old PKZip stream cipher: an "homemade" stream cipher which turned out, with all the unavoidability of Death in a Greek tragedy, to be weak; the stream cipher relies on several internal "keys" which can be unravelled one by one. I encourage people interested in cryptography to study that example, because it demonstrates quite well the way a cryptanalyst thinks, and why mere accumulation of operations does not guarantee security; and the attack is light enough to be implemented in practice (total cost is around 238, which is within range of a few hours of computation on a PC with decent programming, not necessarily optimized assembly).

A lot of cryptosystems from before the computer era were breakable on a per-character basis, because they had to be executed by the human brain of the operators, and such tools are not good at using large values or doing a lot of operations. The classical transposition and substitution ciphers (a very large family) tend to fall to character frequency analysis, which is, indeed, a per-character break.

  • There will of course certain "possible" combinations which will decrypt a small portion of the first block maybe even giving you the first character or 2 in a known file header , but of course none those will actually get you any closer to a actual decryption key. – Damian Nikodem Feb 9 '15 at 18:12
6

Yes.

The current best-known example isn't strictly character-by-character, but Wi-Fi Protected Setup splits the key in two halves and verifies them independently, which permits an attacker to brute-force the first half and then the second half (and makes doing so much easier).

Less well-known but possibly more damaging are various timing attacks where verification of a key, password, or other secret is done on a byte-by-byte basis, returning failure on the first mismatch. This lets an attacker know the first incorrect byte when guessing the secret, so they can figure it out one byte at a time.

Since this is a known type of attack, good cryptosystems are designed to prevent it, but as the WPS example shows, there are a lot of cryptosystems out there that aren't well-designed.

2

Certain side channel attacks, such as Differential Power Analysis, work by recovering key material one bit at a time. They send a statistically significant number of encryption requests through the processor, and watch power consumption that may indicate a certain operation happened. For example, when the key is rotated left in DES after each round, the CPU might consume more power if it has to carry the one.

It would certainly be possible to display the recovered bits as the attack progresses.

1

I'm not aware of any real-world cases where this is possible. There are some cryptosystems where weaknesses have allowed you to learn about specific bits (i.e., RC4 keystream bias), but even these are largely theoretical weaknesses.

Movies and TV shows portray security (and many other topics) in a way that is intended to be fascinating to your average viewer, not technologically accurate. Having a bunch of GPUs cranking away for hours or days and then suddenly getting an answer: not interesting. Similarly, staring at Burp proxy, not interesting; writing a GUI interface using visual basic to track the killer's IP address, interesting.

  • Or a worm virus sliding across the screen like in Swordfish. Mostly the IPs also tend to point to 192.168.x.x – Lucas Kauffman Jul 15 '14 at 5:49
  • 1
    I prefer my IPs to have more than 8 bits per octet, like 23.75.345.200. – David Jul 15 '14 at 14:54
  • I think it would make for a riveting to series where some case is based around a good guy being able to "hack" into the badguys website, it would be filmed in a similar format to the series 24, and would pretty much be some dude typing away at his computer for hours , drinking energy drinks all day and night , chain smoking, and ordering pizza for 11pm so he can claim that he ate for the day. Then after 72 hour long episodes he mutters he yells wooooo calls the cops that gave him the job and then hops into bed to sleep for 3 days straight . – Damian Nikodem Feb 9 '15 at 18:07
-2

The answer is yes, the brute force method could give you one character at a time if do it in an order. Here's why:

Consider the binary code of the password, which would be n bits long. If you set the first bit to 0 (or 1) and try all possible combinations with the remaining bits and none of them work, you know that the first bit is a 1 (or 0). You then do the same to the next bit and so on, revealing more and more of the password. Eventually you have enough bits to form a letter, if that is how you prefer to read it.

You can see that with each letter the password becomes exponentially easier to solve, and if the password isn't random it becomes easier to guess.

  • 2
    This doesn't work. Say the first bit is a 0 -- you won't know that until you've correctly guessed the entire password. The only password that gets fully revealed character-by-character with your method is the password where all bits are "1". – Mark Sep 11 '14 at 0:51
  • Yes, it could find the whole password first - but it could also find only some letters first. You could randomize the value you choose for each bit or use some kind of system of choosing values that are more likely to be used in passwords. Point is that the classic scene where some letters are displayed as solved while others are still unknown is possible. – user55318 Sep 11 '14 at 1:08
  • 3
    It doesn't matter if you randomize or not. My point is that the only password that can be found character-by-character using your method is the one you guess to exhaust the password space. Every other password will have a large chunk successfully guessed in one try, and half the time you will guess the password in its entirety before you are certain about any single bit. – Mark Sep 11 '14 at 1:13
  • This system will obviously not work. The application will not confirm the password as correct until you have guessed the entire password correctly. Yes, the system will confirm the password is incorrect, but that doesn't really help you. For a password of n-bits you would have to cycle through *n*^2-1 bits before finding the correct password. – Chris Murray Sep 11 '14 at 8:04
  • You can have some digits confirmed before you're done. Consider for example a 4-digit combination lock using numbers 0-9. If you start from 0 and try all combinations in consecutive order, you may reach 9000 with none of them having worked. You will then know that the first digit is a 9 - even though you won't know the whole password. If you then decide to try the rest backwards, you may reach 9100 with none of them having worked, so you know the password begins with 90**. – user55318 Sep 11 '14 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.