Seven Codes You'll Never Ever Break | Hacker News Reader

Seven Codes You'll Never Ever Break

wired.com

55 pointscyphersanctus45 comments

Unpaginated: http://www.wired.com/dangerroom/2012/12/codes/?pid=1708&...

Added in edit: Interesting that someone downvoted this comment. Did someone fat-finger it, or do some people really think it's wrong to give a link to the unpaginated version? I'd like to know. If you feel unable to reply here, then feel free to email - address is in my profile. Thanks.

I, for one, appreciate unpaginated links, so thank you.

Stupid title.

Just because Kryptos Part IV hasn't been broken so far doesn't mean that it won't be. It was designed to be broken.

Oh, wait, the actual title is "7 Codes You’ll Never Ever Break" instead of "Codes Hackers Will Never Ever Break". The actual title is more likely to be true, especially given the complete crackpots that appear in groups like Kryptos with outlandish 'breaks' to the codes that are complete crap.

Breaking codes is hard, takes a long time and requires method. Most people won't break these codes.

I know, would anyone like an 8th?

    641648018FD15E9157AB76299C47FFCC9974EB401494D13398A9F2635F66AD83

Spoiler alert: It's just /dev/random

Spoiler alert: That makes it not a code.

Well, I could at any point in the future produce a one-time-pad keystream that decrypts it to a plaintext message.

Also, my comment about it being /dev/urandom may have been pure misdirection.

At some point, someone will just brute-force these.

One of the codes may be a one-time-pad reference to a book which may no longer exist OR the ciphertext may simply be a meaningless fraud.

Another is probably written in an invented, private language.

Two others are short enough that brute force approaches will almost certainly create false positives.

In general, brute force can only work if you have some idea of what to expect the clear text to look like.

So 2 of these probably aren't even codes, just gibberish.

So what if false positives are created? We can just brute-force the analysis of those to find the right one. Are you forgetting the sheer magnitude of quantum, digital, & human-analog computing power we have available today?

I think you're forgetting to check your hubris at the door.

Given the folks who've attacked these problems, the ones that have yielded to brute force thus far: 0.

You can't brute force if you don't know the cipher. Heres an example: Imagine a code that smartly encodes and hides spoken voice. No amount of brute force would be able to crack that.

We can brute force all possible ciphers. Then brute force all of the outcomes that are 100% dictionary words. If those all fail, then we go back to the ones with a few dictionary words missed, and brute-force those. For computers and humans, this is just pattern matching, and brute-force means we have unlimited time and resources to map the entire patternspace find the correct pattern.

You're going to have to quantify "smartly" into something more objective before you can use it in this argument.

Brute-force all possible ciphers? We don't know the input, only the output. But brute-forcing in this context would mean trying out every cipher with every input, and that's not possible since there is an infinite amount of inputs.

I'm not sure where you're getting an infinite number of inputs. The way I understand one-time pads, based on a skim of the wiki article you linked, is that you're taking two strings of letters, one is your message, the other is a random, one-time string, adding them, and taking the modulus of 26.

Where else do we have 2 mixed streams of information? Music. Optics. So we take the input and reverse the mod26, one step at a time, basically creating an array of "demodulated" input values, then I feel as though we should be able to do a Fourier analysis to separate the 2 strings of numbers.

"a cipher (or cypher) is an algorithm for performing encryption or decryption"

So when you say "cipher", that means you want every possible algorithm. Since algorithms can produce output shorter than the input, you get the infinite amount of inputs.

With one-time pads, fourier analysis would only work if the key is not truly random.

How do you reverse a "mod26"? You can't. I give you the number 17. You know this number is produced using the equation: "SECRET mod 26 = 17". How do you know if 43 or 69 was the input?

How do you know they're not one-time pads?

What if we try every possible combination of one-time pads? This is like sculpting with Michelangelo - the correct pattern exists, we just have to remove all of the incorrect patterns from the patternspace.

With one time pads, you can decrypt it to anything, it all depends on the key. See http://en.wikipedia.org/wiki/One-time_pad#Attempt_at_cryptan...

What am I missing here?

So use all keys. Then sort the result and continue to brute-force the correct output.

How many billions of NTLM keys can a Geforce crack in a second? How is this cryptography problem so greatly different than that one?

> How many billions of NTLM keys can a Geforce crack in a second?

According to https://hashcat.net/oclhashcat-plus/ , it's approximately 2.5 B.

This corresponds to a one time pad message of just under 4 bytes long. The difference, of course, with NTLM is you know when you've found the right value. With OTPs, all decryptions are possible and equally valid.

You are missing that when bruteforcing a one time pad you will get all possible arrangements of all letters. How do you tell all the plausible looking strings apart? What kind of a sort function could you apply?

Bruce Schneier broke these codes before breakfast, and now he's gonna break you! http://www.schneierfacts.com/

Thats brillianty funny, now us geeks have our own chuck norris.

There is also Jeff Dean: http://www.quora.com/Jeff-Dean/What-are-all-the-Jeff-Dean-fa...

Grr, of course the link to "drawings of naked women" is broken. Anybody has the correct URL?

For your delight and delectation, here's a link:

http://brbl-zoom.library.yale.edu/viewer/1006200

For reference, a simple Google search found it in about 30 seconds.

Delightful, thanks!

You can find a PDF version here: http://archive.org/details/TheVoynichManuscript

On decoding the Voynich manuscript, http://www.edithsherwood.com/voynich_decoded/

semi-offtopic: how could one crack a cyphered text if it was written in a 100% invented/artificial language, with no relation to any natural language, not even good word-to-word mapping (imagine a pictografic language like the assian ones, but unrelated)? where would one start without word-frequency analysis or something similar to begin with?

Maybe the Voynich manuscript has such a completely imagined language, and that's why nothing worked (if it's not a "hoax:, of course).

A 100% artificial language can be equivalent to a one-time pad, so there's no guarantee it could be cracked.

So if we were to have to make sense of a crypted message from an alien civilization we knew nothing about, this would be equivalent with cracking a one-time pad cyphered message and therefore simply impossible? (this is the original context I thought of when asking the top question actually)

Why can't we brute-force one-time pads? Did someone figure out how to create infinite combinations of 26 letters? As far as I understand, this space is finite, and thus can be brute-forced.

The thing about a one-time pad is that the size in bits of the pad is the same as the size in bits of the message (before and after encryption). So given an encrypted message, the number of possible one-time pads is equal to the number of possible corresponding cleartext messages. There's no way to brute force that -- if you tried every single possible one-time pad to decrypt the ciphertext, you'd end up with every single possible cleartext message, with no way to distinguish which was the original cleartext.

So for every iteration, we get a cleartext message?

So every cleartext message is 100% dictionary words and absolutely no gibberish?

So every cleartext message has complete, logical sentences?

So the complete, logical sentences in each message make sense in the context of the message?

I do not believe this to be the case. Only one cleartext message would actually make sense.

> So every cleartext message is 100% dictionary words and absolutely no gibberish?

No, but for every sensible message there is a way to guess a key that decrypts the given ciphertext to it.

Right, so we just throw out the ones with gibberish and brute-force the remainder.

But 'the reamainder' amounts to 'every non-gibberish sentence of the appropriate length in the target language' with no way to distinguish between them. So

    "Attack at dawn."

and

    "Attack at dusk."

are equally valid and equally probable decodings of the ciphertext:

    739B912B0B067A9B803C46FBDB1E03

Brute force amounts to making a large number of guesses. But you can't brute-force something if you have no information about whether not a specific guess was correct.

This means you have to extend your concepts of brute-force and guessing to include determining which cleartext message is the correct one. If the message is that short, then indeed there is no way to determine from the message alone. Yet even this example gives us tons of info -- we know the attack won't come near midday or midnight, so we only have 2 times to prepare for an attack. This isn't as good as knowing exactly when, but it's better than having no idea of when.

This feels like a skill used by those who guess on tests.

It's not just two messages. The key (sometimes called a keystream) is as long as the message itself, so one can construct any message just by selecting the appropriate key and no information is revealed about whether or not this plaintext is correct.

An attacker may as well just try to guess the message directly and thus dispensing with the pointless process of guessing a keystream and XORing it with the ciphertext.

This is the feature of One Time Pads that gives them a kind of provable security that is not possible to prove for any system in which the key shorter than the message.

There has to be a way. This is just a signal with an approximately equal amount of noise intentionally applied to it.

You're making a fool of yourself. Try again to look at the basic concept. For EVERY POSSIBLE cleartext of the correct length, there is a key that decodes your ciphertext to it. Every. Possible. Cleartext.

Pick whatever method you use to decide if a cleartext 'makes sense'. EVERY POSSIBLE message that fits your criteria will be output during the brute forcing process.

You don't seem to realize just how nigh-infinite the number of different keys there are. If I give you a kilobyte blob of one-time-pad data, it could be any [sub-minute-long] sentence that has ever been spoken or ever will be spoken in the history of the human race, in any language.

I can explain it a different way, that will explain how you can kill the signal. Okay so the original message has 0s and 1s.

1. What happens if we take a 1 and have a 50% chance of flipping it: we get a 0 50% of the time and a 1 50% of the time.

2. What happens if we take a 0 and have a 50% chance of flipping it: we get a 0 50% of the time and a 1 50% of the time.

3. What happens if we know someone had a 0 or 1 and had a 50% chance of flipping it: we get a 0 50% of the time and a 1 50% of the time.

4. What happens when we try to figure out the original bit: Well both 0 and 1 have the same output, so it is fundamentally impossible to figure it out without knowing if they flipped it.

5. Repeat for every bit. Store which ones you flipped. Congratulations, you have a one-time-pad utilizing the XOR method of application.

Also you're right that adding noise as in addition won't mask a signal, but we're not 'adding'. We're looking at the signal, and the completely random noise, and marking down whether they match or not. If I tell you that bits 1, 2, 3, 5, and 8 matched my coin flips that doesn't tell you a single thing about what my data was.

> There has to be a way.

No, there isn't a way. Seriously.

Shannon proved it rigorously. It's also intuitive if you understand how a OTP works. This is probably the most solid proof in all of cryptography.

http://en.wikipedia.org/wiki/One-time_pad The final discovery was by Claude Shannon in the 1940s who recognized and proved the theoretical significance of the one-time pad system. Shannon delivered his results in a classified report in 1945, and published them openly in 1949.[3] At the same time, Vladimir Kotelnikov had independently proven absolute security of the one-time pad; his results were delivered in 1941 in a report that apparently remains classified.

The Dorabella cipher has been solved: http://unsolvedproblems.org/S12x.pdf

No, it hasn't.

Did you read his 'explanation'?

First the decrypted code is close to gibberish and second he starts by creating the key by removing duplicated letters and yet the key has two Ns, three Is, two Ys, two Ws, etc.

Reply on news.ycombinator.com