3
$\begingroup$

Goal

Create a computational puzzle that is fast to generate, takes an average computer minutes to solve, doesn't have any exploitable weaknesses, makes use of existing/tested encryption algorithms

Problem

Let's say we have a string: "Prefix: LLLLLLLLLLLLLLLLLLLLLL" where L can be any alphanumeric character, "Prefix: " is a pre-set prefix, and "LLLLLLLLLLLLLLLLLLLLLL" the solution to the puzzle.

Let's pick 3 encryption algorithms (as an example), AES256, Triplefish, Camellia

The puzzle-creator takes "Prefix: LLLLLLLLLLLLLLLLLLLLLL", encrypts it with AES256 using key_AES256, then Triplefish with key_Triplefish, then Camellia with key_Camellia, resulting in a daisy_chained_puzzle

To the puzzle-solver, the puzzle-creator sends daisy_chained_puzzle, key_AES256 with 1-character prefix missing, key_Triplefish with 1-character prefix missing, key_Camellia with 1-character prefix missing

The puzzle-solver exhaustively tries all combinations of those 3 missing characters, and returns the solution once it stumbles onto a decrypted solution with "Prefix: ", and deducts that the solution is the suffix "LLLLLLLLLLLLLLLLLLLLLL"

Worries

Would the provided "Prefix: " provide a weakness that can be exploited?

Would providing the suffix of each key result in a weakness?

Question

Can encryption algorithms be used daisy chained like this to create a simple computational puzzle / which encryption algorithms would be ideal for the task?

$\endgroup$
  • $\begingroup$ Like a block chain kinda..? $\endgroup$ – Paul Uszak Nov 5 '17 at 15:06
  • $\begingroup$ More like an on-demand/simple proof-of-work system, that uses encryption instead of hashing $\endgroup$ – Conathan Rypt Nov 5 '17 at 15:24
  • $\begingroup$ Tested the method with only AES256 by not sending the first 5 characters of the key with a 64-character random string, the random decryptions are mostly 6-7 characters at best, only the actual decryption is 64 characters, therefore the prefix isn't needed, a simple hash for verification would do. I don't know much about cryptography, but I'm guessing there should be an accompanying weakness with the method too $\endgroup$ – Conathan Rypt Nov 5 '17 at 16:31
3
$\begingroup$

Taking away the worries

Would the provided "Prefix: " provide a weakness that can be exploited?

No, any secure cipher should be protected against plaintext attacks. To be precise, the ciphertext should be indistinguishable (not leak any info) for Chosen Plaintext Attacks. This is abreviated to IND_CPA. This is a stronger notion than just a known plaintext: it lets the attacker choose the plaintext message.

Would providing the suffix of each key result in a weakness?

No, keys of symmetric ciphers should generally consist of random bits. Random means that there is no relation between the various bits within the key. As there should be no relation, it should be impossible to get any information about other parts of the key.

Obviously this is not just a property of the cipher but it should also be a property of the key generation method. As the key consists of random bits, the key generation method is simply the random number generator used. So you must use a well seeded PRNG (e.g. simply /dev/urandom on Posix machines).

This is also true for, for instance HMAC, in case you follow e-sushi's advice and use a hash based Key Derivation Function (KDF) instead of a chained cipher.

The answer

Can encryption algorithms be used daisy chained like this to create a simple computational puzzle / which encryption algorithms would be ideal for the task?

Yes, you can daisy chain them, but please read on.

There is no specific encryption algorithm that makes more sense. If you really want to use a cipher you could use the cipher to create a MAC algorithm (AES/CBC-MAC or AES-CMAC) and chain that.

AES would be preferable simply because there are plenty of platforms that accelerate the block cipher. With regards to compatibility with your goal: any modern cipher will do; neither of your algorithms have been broken and all use a large block size, which would be beneficial to the task.

In that sense, Threefish would be a good choice because of the large block size. That block cipher was designed for chained use in hash-like algorithms, mainly Skein of course.

Unless your goal is to let people try different symmetric algorithms there is no good reason to choose different algorithms; you might as well just choose one block cipher and use it multiple times.

Alternatives

Block chain technology, which this is a clear example of, is usually based on hash functions as e-sushi already mentions - in that case the goal is usually to find a specific pattern of bits (prefixes of 1 bits) in the randomized output of the hash functions - the benefit is that you can easily tweak the amount of output bits that you are looking for to increase or decrease the time looking for the answer.

Then again, the time required to find anything is randomized as well, so although you can tweak the difficulty the time to find the answer is undefined (i.e. you can only tweak the average time to find one or more answers).

A password based key derivation function (PBKDF) such as bcrypt, scrypt, PBKDF2 or Argon2 makes more sense if you're looking for more control for the time to find an answer.

$\endgroup$
3
$\begingroup$

Can encryption algorithms be used daisy chained like this to create a simple computational puzzle…

It can be done, but remember encryption algos are built to be (among other things) fast/speedy while hash algos generally tend to be slower (which is the main reason why — as an example — Bitcoin uses SHA256d for its POW). This is one of a few reasons I would recommend to not use encryption algos for blockchain-alike Proof Of Work thingies.

Instead, I would recommend using hashes. An alternative would be hash based MACs (HMACs) as they allow to tweak things using a secret (what some call the password value) or maybe even things like Argon2 which allow further tweaking which (among other things) can influence speed (read: hardness to solve, while avoiding some of the main probs arising from potential ASIC and GPU implementations).

…which encryption algorithms would be ideal for the task?

Depending on the length of your puzzle, it's going to be less a question of encryption algo, but more a question of algo type (stream cipher or block cipher) and (when using block ciphers) the mode of operation.

Last but not least, related to your

…takes an average computer minutes to solve, …

you should be aware that computer systems differ greatly and recent CPUs even have AES functionality embedded which raises an even bigger problem when trying to balance out the several systems out there to make your puzzle fair.

$\endgroup$
  • $\begingroup$ A little more succinctly: Find a key $k$ under which $\operatorname{AES}_k(\text{hash of block})$ has at least $\delta$ leading zero bits. is a perfectly good substitute for FInd a goober $n$ under which $\operatorname{SHA-256d}(n \mathbin\Vert \text{hash of block})$ has at least $\delta$ leading zero bits. as a problem whose work takes a predictable and controllable amount of computational effort. The specific values of $\delta$ might vary, but you can choose them in each case to make the effort comparable. $\endgroup$ – Squeamish Ossifrage Nov 5 '17 at 16:58
  • $\begingroup$ @SqueamishOssifrage Related to your 1st comment (which you now deleted): I never said or indicated SHA-256 was designed to be slow. I wrote (quote) …while hash algos generally tend to be slower… when being compared to encryption algos. $\endgroup$ – e-sushi Nov 5 '17 at 17:00
  • $\begingroup$ The speed of AES or SHA-256 on a single input doesn't really matter. What matters is the reliable growth curve of the cost of solving the problem as a function of $\delta$, the required number of leading zero bits for a solution. $\endgroup$ – Squeamish Ossifrage Nov 5 '17 at 17:05
  • $\begingroup$ @SqueamishOssifrage Related to your 2nd and 3rd comment (A little more… & The speed of…), note that my answer starts with an It can be done, but… and later even points to potential pitfalls and things to think about when using encryption algos (like mode of operation, embedded AES functionality on some CPUs, etc). So, I definitely didn't rule out encryption algos. I merely pointed out some encryption algo related points to comsidder and added my hash-based recommendations (incl. Argon2) to it as an easier way to handle that growth curve you mention. $\endgroup$ – e-sushi Nov 5 '17 at 17:06
  • $\begingroup$ After some testing, I'm leaning more towards Argon2/Hashcash-like proof-of-work too, blindly tested AES and Threefish so far for my proposed incomplete-key based proof-of-work idea, with both tests, you can almost never match the exact key length, the random decryptions are always much shorter, doesn't really mean anything blindly, but not confidence inducing either, if the decryptions had seemingly random lengths, I would pursue the idea further - there's also no existing/public research on key breaking when a portion of the key is provided, while the bitcoin/hash methods have been tested $\endgroup$ – Conathan Rypt Nov 5 '17 at 18:01

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.