Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I came across KATAN Family of Ciphers for small domain input blocks . They cipher arbitrary block lengths 32,48,64 but their key size 80 bits only.

Is 80 bits of key size considered safe with against brute force attacks , with current state of art processors ?

share|improve this question
1  
This question appears to be off-topic because the crux of the question is opinion, because what you consider safe is different from someone else. And the nature of the question is not related to cryptography regardless - this is simply calculating the cost of an attack, basic math. –  nightcracker Feb 3 at 14:55
    
I suggest reading up on the cipher itself to find out what the design goal was. The usage of 80 bit keys does not mean much at all, especially does it not mean that an attack has complexity $2^{80}$. Considering brute forcing this keyspace, it's probably at the border of current technology: If you have access to a supercomputer network and a couple of weeks or months time, it's probably possible. –  tylo Feb 3 at 15:32
6  
I think the question is fine, and can be answered rationally. I gave it a try. –  fgrieu Feb 3 at 17:46

3 Answers 3

up vote 12 down vote accepted

According to this source (also available as a graphic) and that raw data (see bottom right number), bitcoin mining nowadays (Feb. 2014) tops $20\cdot10^{15}$ SHA-256 per second, that is over $2^{79}$ SHA-256 per year. I'm guessing that a fraction of NSA's budget would allow this organization to do much better.

Here is said raw data as a graphic. Renewed growth since 2013 is attributed to increased use of ASICs. Bitcoin mining SHA-256 hash rate per year

Thus 80 bit of security can not blindly be said good enough today. Depending on the value of the target, the time frame during which a break makes sense, and how easier (or harder) it is to check a key compared to SHA-256 (in particular due to use of key stretching, and the amount of memory necessary per search engine), 80-bit may be very safe, or clearly not enough.


Addition: I second everything in Thomas Pornin's answer, except perhaps "Right now, 80 bits still seem quite sturdy" which is only valid in some contexts, including the context of the question.

Even considering that breaking one instance of KATAN by brute force likely requires significantly less work than $2^{79}$ SHA-256, in the context intended for KATAN (really low-end devices such as RFID tags), an expectable consequence of such break is to be able to clone one single RFID tag, which is very likely feasible at far lower cost by side channel attack or micro-probing, regardless of key size. So right now 80 bit of key is fine enough for an individual RFID tag key on rational grounds (which discounts the irrationally devastating effect of the announce of any break). That would not be the case if all tags used the same key (a classic mistake), or for the master key from which the RFID tag keys are derived, or some other uses of KATAN.

share|improve this answer
    
Where did you get that this is for RFID tags? $\;$ –  Ricky Demer Feb 3 at 19:22
    
@Ricky Demer: I have heard of KATAN (part of the question) exclusively in the design of low-end RFID device. See e.g. this, which motivates the original design, stating page 12 under "Design goals": "Really Low-end Devices" and mentioning "RFID tag". –  fgrieu Feb 3 at 19:59

A key size of 80 bits is the historical limit of infeasibility; that's what was used in the 1990s as a rule of thumb. That's the reason why Skipjack used an 80-bit key, and SHA-1 offers a 160-bit output. Various people have also estimated that a 1024-bit RSA, DH or DSA key offers an "80-bit equivalent" protection (see this site).

One of the most optimistic formulations of Moore's Law is that every three years, we can put four times as many transistors in a given silicon area, and clock it twice as fast. For crypto-cracking jobs, this would translate to one extra bit per year. In that sense, the "80 bits" of 1994 would be "100 bits" nowadays. However, this view of the "law" is really unrealistic and is not verified in the later years (transistor density has kept one rising, but clock frequency is stalling).

The current public record in symmetric key cracking is a 64-bit keys. The people at distributed.net have launched a 72-bit attempt; after 4000 days (almost 11 years !) they explored 3% of the key space. Right now, 80 bits still seem quite sturdy; going to 128 bits is overkill, but we do it nonetheless to have a large "security margin" (a rather irrational reason) and for aesthetic reasons (a very irrational reason, but hey, "128" is a power of two, and powers of two look good).

share|improve this answer
    
Acutally the version of Moore's Law for raw computing power still holds. The raw computing power still grows exponentially when you take many-core architectures. It can be also seen in the HPC peak performance. The bruteforce attacks can be carried out perfectly parallel, so you can take advantage of it. It actually might slow down a bit in near future, because there is trouble of powering this computing power. Needed power also grows exponentially (with a different factor but still), power sources and cooling have trouble keeping up. –  luk32 Feb 3 at 18:49
    
The law is still exponential, but not x8 every three years, rather x4 every three years (so 12 or 13 key bits for 20 years, not 20 bits). –  Thomas Pornin Feb 3 at 18:59
    
Ok, maybe, but the limiting factor for computing power is not the clock. As you can easily put 2 cores next to each other an double the effective processing power. And in this case this is the real effective computing power, not the theoretical one. –  luk32 Feb 3 at 19:08
    
Moore's law is only interesting if you consider attacking a cipher on a single computer, or a single computing center with a fixed amount of space. But today you can just order raw computing power , e.g. in the Amazon cloud, and then it just comes down to how willing you are to spend the according money. Intelligence agencies (and probably organized crime, too) have their own computing centers and no one knows what they are actually capable of. –  tylo Feb 7 at 12:27
    
@luk32, "you can easily put 2 cores next to each other" isn't actually that easy. Cache access is made slower, more fragmented, and overall less circuitry is available for each individual core (or the circuitry must shrink to accommodate the needed space). It is actually far easier to just purchase a second GPU or a second computer and attack the problem in parallel. Moore's law provides limited insight into large server farms dedicated to this task, or large FPGAs dedicated to attacking these problems. –  kurtzbot 2 days ago
  • It depends on how long you want to keep your data safe for. Do you want the secret safe for 1 week, the rest of your life or forever? Will you get in trouble, put in prison or be killed if that secret is revealed to the wrong person?
  • It also depends on who you want to keep the data safe from. Do you want your data protected from nation state level adversaries e.g. US, UK, China, Russia?
  • Do you want to consider adversaries that could have viable quantum computers already in secret or very soon in the future <5 years?

Let's assume we want to protect the data from a certain agency with a massive black budget ($10,800,000,000 USD per year) and whose mission is to obtain and decrypt the world's communications. Let's also assume they've got viable quantum computers, we know they have been trying to build one and who at one point were about 20 years ahead of academia in the field of cryptography. If they don't have one just yet, they will do in the next <5 years so you need to consider if you want your data to secret for longer than that.

An important thing to note is that when assessing the security against a brute force search, an attacker does not need to perform the full number of attempts. Lets say you have a 128 bit key, that's $2^{128}$ search operations. That's the worst case scenario. If they find the right key after $2^{64}$ operations or $2^{72}$ operations then they can stop there, they've cracked your data. There is probably some statistical analysis that could be used to figure out the probability of finding a key faster than brute force search in a certain key space. Also remember that there are attacks against various algorithms which can lower the number of brute force searches required.

You are hoping an 80 bit key will be secure, which is considered by some to be around the current limits of capability when it comes to adversaries with the top regular supercomputers in the world (taking into effect supercomputers with GPUs and CPUs with AES-NI instructions). In a worst case scenario, this can be cracked in $2^{40}$ time on a quantum computer using the current best quantum search algorithm which is Grover's algorithm. Security of $2^{40}$ is not secure at all.

Given a 128 bit key which is considered by some to be overkill when it comes to adversaries with normal supercomputers, this can be cracked in $2^{64}$ time on a quantum computer which is still not secure at all.

If we move up to a 192 bit key this will take $2^{96}$ time with a quantum computer. Probably the bare minimum security margin nowadays and it might protect your data for a few more years.

If we move up to a 256 bit key this will take $2^{128}$ time with a quantum computer. If we assume $2^{80}$ is within reach of the top supercomputers in the world and with Moore's law they gain an extra 1 bit of processing power per year, then this will be safe until about the year 2062. You might still be alive by then, and you might still want your secret protected. The established totalitarian government might forcibly remove you from your retirement home and throw you in prison because you sent a mere 256 bit encrypted message to your friend talking about going on an anti-government rally back in 2013. Do you want to risk it?

Your next option is going higher than 256 bits to stop them cracking your data in your lifetime, then you can rest in peace. With the Threefish algorithm you can have a 512 bit or 1024 bit key. For a 512 bit key that gives at least $2^{256}$ security against a quantum computer. They'll be there until about the year 2190 working away on that one. You better hope they don't capture you, put you in cryosleep then wake you up again when they've decrypted it just to have proof and punish you.

What about if you never, ever want them to find out the real data? What if you're tired of government sock puppets estimating "safe" levels of key bits and "safe" algorithms for you to use? What about if you want the ability to give them any number of fake keys under duress and still have it decrypt to something plausible so you won't get in trouble? Well then you should use a one-time pad. They can try every key and have it reveal every plausible plaintext but still not know exactly what the real data is. This is the reason spies, militaries and governments use it - plausible deniability. Just don't use a backdoored or potentially dodgy random number generator like Intel's RDRAND. Use a proper TRNG.

share|improve this answer
    
I disagree with "If they don't have one (useful Quantum Computer) just yet, they will do in the next <5 years". I'm ready to bet that there's on our planet no such agency (pun intended) that will get a quantum computer doing anything useful to cryptanalysis in the next 8 years. The leaked document makes it clear that it remains a research subject (thus doubtful) to determine if a useful QC can be built. –  fgrieu Feb 7 at 13:06
    
By the account of Don Coppersmith, Differential Cryptanalysis (which motivates your "20 years ahead of academia") was known to academia by 1989, and to IBM in 1974. Any reference to that agency knowing it by 1969 or earlier? Whatever the offset, I attribute it to a general advance of military cryptography before 1990. For what we know, academia has largely caught-up on a theoretical standpoint (clearly not on the standpoint of brute force, and likely not for interception and other technological attacks). –  fgrieu Feb 7 at 17:17
    
When or how a secret national surveillance agency (pun intended) with a $10.8B pa. black budget will or will not have a QC is just speculation and hearsay really. There's no way to know what their secret quantum computing capabilities at Oak Ridge or Ft. Meade really are. Guessing is pointless. The point is that they are storing all data. Encrypted data is flagged and if they can't decrypt it immediately they store it until they can. So when they do have a QC, your data will be decrypted eventually if using small key lengths. –  NDF1 Feb 7 at 22:40
    
See Bruce Schneier's quote "It took the academic community two decades to figure out that the NSA "tweaks" actually improved the security of DES. This means that back in the '70s, the National Security Agency was two decades ahead of the state of the art." NSA knew about differential cryptanalysis in the 70s and IBM who were assisting NSA at the time with security clearance. –  NDF1 Feb 7 at 22:50
    
Your butlast comment makes a good argument for using wide session keys when things need to be kept secret for a long time, together with a cryptosystem giving forward secrecy: that insures that future breaks of long term keys (by quantum computer if we trust your intuition, or just by some compromise of the system holding them if you ask me) won't allow to decipher past intercepts. –  fgrieu Feb 9 at 17:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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