3
$\begingroup$

Is there a good candidate for an algorithm that would takes n days to break depending on how many bytes of the key are missing? I'm writing a story where you need to collect pieces (bytes) of a key and depending on how you have you get an head start in brute-forcing the message.

The message is around 200 chars long (so quite small). Count on computer resources be what would feasible for a non state-actor (bot nets etc), but still pretty resourceful. The key length / piece length does matter much, but should be viable for 6-8 "pieces"

The main problem I see is that time with brute forcing strong encryption is usually measured in years, or even million of years, and I need it more to be around 3 days per "piece"

$\endgroup$
  • 1
    $\begingroup$ In cryptography, it is quite uncommon to talk about specific timeframes besides "longer than most people even can imagine", because it depends on the hardware and the actual implementation a lot. Micro chips, mobile phones, notebooks, dedicated servers and entire computing centers have vastly different amounts of computations they can do in 3 days. $\endgroup$ – tylo Nov 2 '16 at 13:50
  • $\begingroup$ Yeah, that's what makes it tricky... it doesn't need to be super specific time frame but weak enough to be broken in days but not weak enough to be broken immediately. In the end I guess something that would be feasible is sufficient :) $\endgroup$ – Homde Nov 2 '16 at 13:59
  • $\begingroup$ Since you say this is for a story, I'm assuming it just has to be plausible, not necessarily cryptographically sound. Is that a fair characterization? Probably also technically complex, but simple enough that readers of your story can feel like they understand things. $\endgroup$ – mikeazo Nov 2 '16 at 14:52
  • $\begingroup$ Well.. .I'd like it to cryptographically feasible, even if the details might not be explained in detail I don't want every computer savvy person to go "that's bullshit" :) $\endgroup$ – Homde Nov 2 '16 at 15:36
  • $\begingroup$ @Homde, hmm, that is about how I feel about every "hacker" book/movie I've ever read/seen :) (not to mention anything computer related talked about during the recent US presidential campaigns/debates) $\endgroup$ – mikeazo Nov 2 '16 at 15:51
2
$\begingroup$

You can try 20 billion DES keys per second on a single Nvidia Geforce GTX 1080.

Assuming (roughly) that another algorithm (with much higher keylength than 56-bit) is equally as fast, the bitlength you want for the key is:

$$\log_2(\text{NumberOfSeconds})+\log_2(\text{NumberOfGPUs})+34$$

where $2^{34}\approx 16 \text{ billion}\approx 20\text{ billion}$.

If you want some example numbers, let's do the math:
If we want to wait approximately 3 days (that's $24\times 60^2\times 3$ seconds) and can get hands on maybe the equivalent of 5000 such GPUs using a botnet, that yields about $64$ bits which sounds very reasonable.

What you could do with this is to take AES-128 und give 8 bytes using (8?) puzzles and let them brute-force the remaining 8 bytes. Every unknown byte will increase the brute-force workload by 256.

So TL;DR: Brute-force of 8 bytes (give or take a few bits) sounds like what you're aiming for.

| improve this answer | |
$\endgroup$
  • $\begingroup$ OP is saying 3 days per piece, or a linear work factor in the number of unknown pieces. Wouldn't a normal brute-force be exponential work factor in the number of unknown pieces? $\endgroup$ – mikeazo Nov 2 '16 at 16:09
  • $\begingroup$ @mikeazo hmmm, ... one could use different keys with different prefixes for each piece. $\endgroup$ – SEJPM Nov 2 '16 at 16:11
  • 1
    $\begingroup$ it would almost be like splitting any encryption key into 8 parts, then encrypting the parts each with independent 8 byte keys. $\endgroup$ – mikeazo Nov 2 '16 at 16:25
  • 1
    $\begingroup$ This could even work well in the story. The key was split using information theoretically secure shamir secret sharing. Each recipient of a share, however, encrypted their share with a (human chosen) password. So each share will take around 3 days to brute force. $\endgroup$ – mikeazo Nov 2 '16 at 16:29
  • $\begingroup$ In order to get a linear scaling, I would suggest brute forcing a few bits of an iterated hash function. And the scaling is done by using $1 M, 2M, 3M, 4M ....$ rounds of hashing. $\endgroup$ – tylo Nov 3 '16 at 10:33

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.