Cryptography elements needed for a story

Question

Note: following Maarten Bodewes's answer, I edited this post to make it clearer.

I'm writing something partly driven by the need to crack a few encrypted files.

This is what needs to happen in the story:

There are two parties involved that are trying to crack them, party A and party B. Party A has had them for four years, and despite all attempts, they failed. Party B got the files later on and managed to crack them in less than two months of non-stop trying.

Party A has available state-of the-art tech, but party B are the good guys and this is a sci-fi story, so they have far, far better tech that nobody else has. The details of the technology aren't relevant to the story so I don't need to establish them.

Party B will eventually succeed; still, to keep a modicum of suspense up, it must still be possible for them to fail. By this I don't mean that something throws a spanner in their works; I mean that their decryption attempt, however more advanced than party B's, isn't guaranteed to work. In other words, party B can't just sit and wait until whatever they're doing is done knowing that at that point they will have the decrypted file.

This is what I need:

1. An algorithm such that, if you encrypt a file with it using a high-entropy password, is beyond any brute-force attempts using known methods and tech. (This is why party A fails.) I understand that AES-256 might be what I'm looking for.
2. An approach that will allow party B to succeed nonetheless. The fact that party B has much faster computers available than anyone on Earth is central to the story so you can assume that. However, if brute-forcing these files required ridiculous amounts of energy or other very unrealistic things, I'm not prepared to claim party B has any of that. Other approaches or situations that would give party B an edge—such knowing what algorithm was used, being able to guess details about the password, or knowing about possible key files—are certainly options I would consider. If quantum computers could plausibly break AES, that's another option I would consider because it's not too far-fetched for party B to have them. I just don't know if QC could actually do that.

Answer 1

Though quantum computers fit the requirements, I'm not sure they are the best option. A general purpose quantum computer capable of attacking modern encryption (RSA, AES) would have serious ramifications on society. It's not only applicable to this one cipher you are breaking.

Does it have to be the superior computing resources which gives the good guys the edge? Because I can think of several plausible storylines where the edge comes from a bright idea.

Option 1: Information about the passphrase. If the good guys learn something about how the passphrase used to derive the encryption key was chosen they could easily reduce the search space time from millennia to months. For example the passwords are always lines from a book where some of the words are replaced with the first letter. Or something else. One way to learn such a pattern is they crack some other password picked by the same person which was encrypted with weaker encryption. The hero recognizes the pattern in this other password hypothesizes it may be a common method of selecting passwords and starts a brute force dictionary attack on the reduced space.

Option 2: General Cryptanalytic improvement. Our hero is a master cryptographer. And uses an unknown but plausible cryptanalytic attack on AES to greatly improve speed. This attack could have greatly reduced runtime and it could work on only a fraction of the keys. It could be discovered that a sizeable fraction of keys have some undesired property which makes a superior attack possible (which still requires great computational resources) and they are unsure if the key happens to be such a weak key, they are likely to be able to quantify their success probability in advance.

Option 3: Identifying a flaw in how the data was encrypted Whoever encrypted the data may have messed up. And accidentally left an easier route to attack it. It could be something like applying error correction after compression before encryption (the flaw in GSM). Or something which more directly leads to an attack like keeping a simple hash of the password. The heroes find this flaw and launch a more efficient brute force based on it.

Option 4: Attack the message not the key Out heroes don't try to crack the encryption at all. They utilize knowledge of message and compression system used. and find what possible messages would result in desired size. Though if it's only size it's only viable if we had a small collection of possible messages and the attack will be quick. There are attacks on voice for example where we use size and timing to decipher words and phrases without breaking the encryption.

Answer 2

Party B will eventually succeed; still, to keep a modicum of suspense up, it must still be possible for them to fail

An approach that will allow party B to succeed nonetheless

To me the obvious solution is strategy and HUMINT.

With algorithms at the time, say bcrypt and AES-256, plus a high entropy password, party A would spend eternity either attacking the key directly or trying to bruteforce the password. The sun would literally burn out before they succeed. Thus the only option is to discover the correct password, or get very close so they can brute force a similar password derived from what they think it might be.

And thus the best, possibly only option is to use intelligence gathering, psychology, social engineering , etc., trying to figure out what kind of password would have been used by whoever encrypted the files. Maybe they used a similar password on a website that did not use good key derivation (md5), maybe it is something from their past, like a favorite quote. Either way, the frantic search for intelligence gathering, sending people out to research, talk to old friends and colleagues, would probably make for an engaging storyline.

Answer 3

It's nice to see SciFi authors consulting professionals for technical viability problems. I've got something on my mind for you to consider.

This is what I need:

An algorithm such that, if you encrypt a file with it using a high-entropy password, is beyond any brute-force attempts using known methods and tech.

There was a joke a while back in the NIST Post-Quantum Cryptography Standardization project, Daniel J. Berstein proposed pqRSA (which is just RSA with rediculously large public keys) for public-key encryption and digital signature. I think you could say the files are encrypted with 3072-bit Elliptic-Curve ElGamal

An approach that will allow party B to succeed nonetheless

Quantum computers of course, but party B must use their special/innovative/patented technology to make some kind of huge breakthrough.

I'd recommend the story progress from party B attempting to entangle 8192 qubits into superposition, to them successfully implement extended Euclidean Algorithm (EGCD) over the qubits.

These are actual current engineering challenges! As of August 2020, we've yet to exceed 100 fully-controlled qubits.

Answer 4

A real-life example:

We had a zip file encrypted w/ the older, rather weak encryption algorithm, used before the introduction of AES-based encryption in the ZIP format.

There are brute-force tools to crack ZIP file passwords, there is also a peciliarity of the particular encryption that allows for very quick check for 65535 of every 65536 passwords. Those 1/65536 of the probable passwords that pass the first test need to decrypt a whole file in order to see if it is the actual password.

The ZIP file contained a stray Thumbs.db file.

The first person approaching the task removed the Thumbs.db file from the ZIP as no one needed it in the first place (a misguided optimization) and then ran the brute-force tool. It ran for a lot of time on a rather powerful machine - and failed.

The second person got only the Thumbs.db file as it was a lot smaller than all other files so it could decrypt and decompress faster at each attempt. They removed all other files from the ZIP. They used for the possible password the alphabet native to the author of the ZIP file and only capital letters (deducing the habits of the author from the file names and other available info). They had success in 2-3 days using a lot weaker hardware. The password cracked against the Thumbs.db file happened to work for all other files in the archive.

To paraphrase Al Capone: You can get much further with a brute force and an educated guess than with a brute force alone.

Answer 5

I don't really like your setup. Party A has available state-of the-art tech, yet party B wins because they are the good guys while they are both doing basically the same is a bit unrealistic. It could happen that both parties try at random and one is just luckier (and, oh surprise, they are the good guys).

I would recommend on making party B have an advantage based on having better knowledge on the subject who encrypted it. So for example, party A killed brilliant scientist (let's say Albert) and robbed his plans of a XYZ. Party B (after getting a copy, 4 years later) wants to avoid those falling into the evil hands, and have helping them an old friend of Albert / his widow / an apprentice... This gives party B an advantage, as they may know some of the passwords Albert used, and thus hypothesize the likely structure of the password they are looking for.

Or both parties may know that Albert probably used a pet name with some added numbers / symbols. While party A bruteforcing is based on lists like Top 1200 Pet Names, Albert friend suddenly remembers (after an evening with his niece) that the first pet of Albert was named after a Pokemon, which then made party B work from a completely different list.

Answer 6

These files were encrypted in 2003. AES is from 2001 if I'm not mistaken, so that's possible, right?

Sure. The Rijndael algorithm was first published in 1998, so that's a 5 year gap.

Party B gets the files only later on and manages to crack them in less than two months of continuous trying.

That's not possible if they are well-encrypted. Either the passwords are weak enough or a different attack is found.

Details of the tech aren't relevant to the story so I don't need to write about them, but I want to avoid writing things that just don't make sense

Such as requiring more energy that available in the solar system? We're talking AES-256 here.

My first guess would be that, advanced as it may be, their tech has limits too and there is such a thing as a password long enough to make their attempts futile.

Sounds a bit boring, what about a hardware failure or power outage?

Is it possible to figure out what encryption algorithm was used if all you have is the encrypted files themselves?

Depends on the protocol really, otherwise no, probably not from just the ciphertext. With AES and the file date, just guessing the protocol / AES would be good.

To make it interesting you could maybe specify an attack where classical analysis is combined with quantum analysis that speeds up the classical analysis more than Grover's law would allow for. AES is not provable secure after all, so better attacks can be found.

Answer 7

Party B could discover that the key was generated from a password and the details of the Key Derivation Function used. Then instead of attacking the encryption key, they can attack the password, which could reduce the number of possibilities to the point where their advanced computers can find the right password in a couple of months.

Answer 8

Depending on what your definition of "the good guys" is, you could have a backdoor that has been subtly leaked into the algorithms. The famous DUAL_EC_DRBG would be a case study on this. Of course, since you can use a fictitious algorithm, there's no need for it to be obvious that the particular back door always works. The bad guys could have picked different keys, but thanks to social engineer, there's a really good chance that they picked keys that were publicly recommended, but weak.

Another possibility is that the algorithm has a flaw which affects the encryption with some probability. Say, 98% of keys are actually poor keys which permit an attack, while 2% are resilient to it. This sort of thing could easily be overlooked if one is using Big-Oh notation when analyzing the proofs. There are plenty of systems which are NP (vaguely meaning "brutally hard to solve"), but only for the worst case. We try our very best to avoid this happening in cryptography, but the whole point of attacks on cryptographic systems is that they do something we didn't think of on the day the algorithm is released.

While this is Crypto, not WorldBuilding or Writing, I'd be remiss to fail to mention Sanderson's First Law of Magic:

Sanderson’s First Law of Magics: An author’s ability to solve conflict with magic is DIRECTLY PROPORTIONAL to how well the reader understands said magic.

His law of magic applies to technobabble too. You can get away with a lot, cryptographic wise, as long as you follow that law.

And never underestimate the power of rubber hose cryptoanalysis!

Answer 9

Read Neal Stephenson's Cryptonomicon, then read discussion of a significant flaw in the algorithm constructed for the story. Read a bit about the background to analysis of Enigma (Wikipaedia is entirely adequate for this). Then go back to what you're doing :-)

One scenario is that the crypto is easy enough to solve by hand, provided that you know its flaw. And discovering its flaw is vastly easier if you have the computing power to wring every bit of statistical information out of the messages.

As a specific example, Cryptonomicon alludes to an unbroken Japanese cipher. However the gist of messages encoded in it could be determined, since the protagonist had sufficient (and unprecedented) computing power at his disposal to be able to detect the effects that the messages had (e.g. that the Japanese were suddenly looking for mining engineers).

Answer 10

To me, the idea related to a password and a KDF is the best to fit your scenario here. This would require that Party B, by some means, have learned which KDF was used to generate the key, while Party A did not have this information. Therefore Party A is doing a brute force search on the entire keyspace (which will take an eternity), while Party B is only doing a brute force search on the input passwords to the KDF.

If you want to add suspense, maybe Party B doesn't actually know the KDF that was used, but uses some clues about when and where the original encryption occurred to make an educated guess about which KDF was used. Then, the suspense comes from the fact that, while brute forcing passwords for the given KDF, there is no guarantee that they picked the right one.

This also has a nice narrative element because it shows the good guys thinking of something more clever than the bad guys, and taking a risk on it being true, which after 2 months of uncertainty happens to pay off. During the 4 years preceding, an intelligent Party A may have tried this same strategy as well with all the KDFs it thought could have been used for the files; Party B can use the fact that Party A has not been successful yet, to infer that the KDF is not one of the obvious choices, and thereby narrow down and make some theory of what kind of less common setup could have resulted in such a key.

Answer 11

Another option can be that, these files are encrypted using pairing-based IBE.

Pairing is an elliptic curve operation on 2 ECC points (from the same or different ECC curve) that results in a finite field element.

IBE is identity-based encryption. The encryption key is the identity/name of the recipiant, and decryption key is generated from a master private key using a key escrow mechanism.

Party B can, by their technological supremacy, able to find that the ephemeral variable $k$ is static in all ciphertext (Sony used ECDSA for signing their PS3 console games, and the private key leaked because they failed to sign developer certificates with unpredictable $k$)

Party B then find out there was an obfuscation applied to the curve parameters used in the pairing operation (I'm making this up, I'm not an expert in pairing-based cryptography, but that seems somewhat plausible to me), but by some chance, they find there was a 3rd curve that can be used to work around the obfuscation.

Finally party B used some kind of quantum-classical computer combination, enumerated the 3rd curve, and managed to recover the master key, thus find out all of the escrowed decryption key.

Answer 12

You are asking for: "An approach that will allow party B to succeed nonetheless."

It's probably not a good idea to present in technical terms the benefits of one algorithm over another as they exist in 2020. You said you're writing a story. You probably want it to make sense to a wide audience, but not look stupid like the password-cracking session in Clear and Present Danger (1994).

1. Party A attacks the blind entropy of the password, and fails after expending huge amounts of computing resources (e.g. AWS EC2, perhaps using a stolen credit card).
2. Party B attacks the human aspects of the password, and succeeds while expending far less computing resources (e.g. a monster gaming rig they build themselves).

A strong password still needs to be memorable and convenient to type. A strong password is often required to have an upper case letter, a number, and a symbol. From past password cracking competitions I have studied, a sizable fraction of those passwords fit the pattern of starting with a capital letter, followed by all lower case letters, followed by a number, and ending with a symbol. In your story, party B designs its brute-force password cracker to only use that pattern, reducing the combinations of tries needed by a factor of several powers of ten.

Answer 13

To be honest, there doesn't have to be anything clever here. Simply trying brute force - i.e. try all combinations, on a good cipher will work for the narrative - that's because while it is true that you can't guarantee decryption before trying all keys, it is also true that Party B might win on the first try, or at least an 'early' one. So B starts later, but has better tech so is catching up, but can't guarantee a win until it comes (suspense as requested). The only issue with a good cipher is whether either of them would bother wasting their time - because it is unlikely either would succeed. But they could - and this is fiction.