19

Can some one simply explain the meanings and the difference between symmetric key and block size.

Why 64 block size not safe any more and they increase it to 128 (AES,...,Serpent)? And what about key size?

CodesInChaos
  • 11,964
  • 2
  • 40
  • 50
rezx
  • 1,069
  • 3
  • 12
  • 21
  • 1
    tried to reword this to be more readable - hopefully I haven't broken the meaning. – Rory Alsop Jun 07 '12 at 13:23
  • @ rory its the same :) – rezx Jun 07 '12 at 15:55
  • Excellent - just trying to clarify for our audience, which while international uses English here. Anything you can do to use proper spelling and grammar will help, especially those who aren't native English speakers. – Rory Alsop Jun 07 '12 at 16:00

4 Answers4

15

A symmetric key algorithm is one which uses the same key for both encryption and decryption. Examples of symmetric key algorithms are AES, 3DES, Blowfish.

An asymmetric key algorithm on the other hand, uses 2 keys, one for encryption and one for decryption. An asymmetric key algorithm is designed in such a way that it is unfeasible to derive the private key from the public key. A common asymmetric key algorithm is RSA.

The term block size refers to the block cipher. Basically, there are 2 types of ciphers.

Stream cipher - The algorithm encrypts/decrypts the message 1 bit at a time.

Block cipher - The algorithm encrypts/decrypts the message block by block, a block referring to a group of bits. Common block ciphers include AES - which works on 128 bit blocks, and Blowfish - which works on 64 bit blocks.

All of this information can be found on their respective Wikipedia entries:

http://en.wikipedia.org/wiki/Symmetric-key_algorithm

http://en.wikipedia.org/wiki/Public-key_cryptography

http://en.wikipedia.org/wiki/Block_cipher

http://en.wikipedia.org/wiki/Stream_cipher

Luke Park
  • 249
  • 3
  • 8
  • @ terry, i remember reading about that before so block mean 'attack at down' will be if blocksize 3 'att ack atd own' right – rezx Jun 07 '12 at 13:17
  • 6
    @rezx No offence, but i'm sorry. I can't understand what you are typing. –  Jun 07 '12 at 13:19
  • what i get now is block size mean the the plain text will cut to pieces like first comment. i cut attack ' att ack' cuz blocksize is 3 only – rezx Jun 07 '12 at 13:26
  • ok i take a look at wiki links for blocksize, But about keysize AES had 128, 192, 256 is that the maximum password cuz DES had 64 keysize and short key AES had 128keysize and long password – rezx Jun 07 '12 at 13:32
  • The size of the password is not related to the size of the key or the block. You can put a password on a key to ensure nobody else than you can use it (in the case of stolen laptop eg.). The size of the key is used to make the cracking harder. Cracking AES 256 will be harder than AES 128 but will be slower also. DES is not good because 64 can be brute forced easily but 3DES (use 3 time the DES algorithm) is better (even if not advised). – Martin Trigaux Jun 08 '12 at 07:26
  • @rezx Yes, a hypothetical cipher with a blocksize of 3 trying to encrypt "attackatdawn" would first encrypt "att", then "ack", then "atd" then "awn". – forest May 15 '18 at 06:46
12

You ask 2 different but related questions.

Why is a 64 bit block size not safe any more and why did they increase it to 128 bits?

In a block cipher, plain text data of a fixed size (the block size) is encrypted into ciphertext of exactly the same size. However, the total number of possible ciphertext blocks is only 2block size, and when you use just the square root of that number of blocks you have a 50% chance of having a duplicate block, which leaks information. The square root of 264 is 232 and 232 blocks of 23 bytes = 235 Bytes = 32 GiB. So on a 1 TiB drive with whole disk encryption you would expect to find approximately 1,000 duplicated ciphertext blocks. (From the formula here: (240/23)2/264) To be fair, a duplicated ciphertext block is not a disaster, as techniques are used to ensure the same plaintext does not encrypt to the same ciphertext every time, so the reverse is also true: duplicate ciphertexts do not necessarily represent duplicate plaintexts. The bigger point is that computing power and storage space have outgrown 64 bit ciphertext blocks.

So current block ciphers use 128 bit blocks which make it unlikely to see a duplicate in Exbibytes (millions of Tebibytes) of data, which should suffice for a while. Most other forms of attack are simlilarly made significantly harder by this increase in block size.

What is the meaning of key size and why is the size important?

The key size is the size of the "secret" used to encrypt the data. In a perfect cipher, you would have to test every possible key to guarantee you could decrypt some encrypted data and on average you would have to try half the possible keys to succeed. When DES was published, 56 bits was a big enough key space to be "hard enough" that brute force was unreasonable in civilian computing. Then in 1998, the Electronic Frontier Foundation built a machine to brute-force decrypt DES for $250,000. Now with the explosion of civilian computing power, particularly the leveraging of enormously powerful parallel computing in GPUs, even 128 bits is only considered secure enough for the lowest level of classified information, SECRET.

Also, no cipher is perfect, and many attacks can recover part of the key, so longer keys provide additional security in that even if part of the key is recovered, there is still a huge key space that remains to be brute force attacked.

Major Major
  • 492
  • 2
  • 9
  • The problematic size isn't 2^{n/2} *bits*, it's 2^{n/2) *blocks*. So most most modes of operation used with a 64 bit block once you approach 32 GiB not 512 MiB. – CodesInChaos Jun 15 '13 at 20:30
  • @Codes, you are correct. Thank you for pointing that out. I have updated the answer. – Major Major Jun 16 '13 at 00:57
  • 1
    "on a 1 TiB drive with whole disk encryption you would expect to find 32 duplicated ciphertext blocks" I don't think that's correct, collision rate scales approx. quadratically. – CodesInChaos Jun 16 '13 at 08:23
  • @CodesInChaos you are correct and I have updated the collision calculation. – Major Major May 14 '18 at 23:27
  • Given the common conservative heuristic that you should only encrypt _2^(s/4)_ blocks with a given key for a cipher with a block size of _s_, it should be safe to use 64-bit blocks if you rekey about once every 512 KiB (65,536 blocks at 8 bytes each). – forest May 15 '18 at 00:18
3

AES, 3DES, Blowfish... are block ciphers. A block cipher is a function which takes as input a data block of a given size (a fixed number of bits) and a key (which is also a sequence of bits, not necessarily of the same size than the block); and the output is another block of the same size than the input block. Moreover, for a fixed key, the function must be a permutation: two distinct input blocks will yield two distinct output blocks.

E.g. Triple-DES (also called 3DES) uses 64-bit blocks, and 192-bit keys (it so happens that the Triple-DES algorithm totally ignores 24 of the 192 key bits, so we often say that Triple-DES uses a 168-bit key; however, standard-compliant implementation expect a 192-bit key, aka 24 bytes).

Encrypting and decrypting blocks is fine, but usually we want to encrypt "messages", i.e. long streams of data bytes, with a length which is not necessarily a multiple of the block size, and which can be quite high (e.g. you can encrypt several gigabytes worth of data). To turn a block cipher into an engine which can encrypt and decrypt messages, you need to use a mode of operation. Making good modes is an art; there are many subtle flaws which can cripple security if the mode has not been well-designed. The block size appears to be an important factor: in most modes, security decreases, sometimes quite sharply, when the input message length exceeds a threshold which depends on the block size; namely, if your block cipher uses n-bit blocks and you encrypt more than 2n/2 blocks of data, then you are in trouble. For a block cipher which uses 64-bit blocks, the threshold is about 32 gigabytes (232 blocks of 8 bytes). When DES was designed, 32 gigabytes were science-fiction; nowadays, 32 gigabytes are a 20$ USB flash drive.

So we now prefer block ciphers with 128-bit blocks. It was a design criterion for the AES.

Key size is an orthogonal issue. Keys for block ciphers are sequences of bits of a given length, which depends on the internal structure for the block cipher. There is no requirement for the key length to match the block size in any way; however, cryptographers are in love with binary, so key length will usually be a power of 2 like 128 or 256, and so will block size be. AES has been defined to use keys of 128, 192 or 256 bits.

What is needed for security is that there are two many possible keys for an attacker to try out all of them (trying all possible keys until a match is found is called exhaustive search). Each additional key bit doubles the number of possible key sizes. 128-bit keys are large enough with a comfortable margin; larger key sizes are there for bureaucratic compliance, paranoiac managers, and developers who feel threatened in their manhood.

Community
  • 1
Thomas Pornin
  • 322,884
  • 58
  • 787
  • 955
  • 1
    Actually, there are two variants of TripleDES in use, one with 168 bits of key data and one with only 112 bits of key data. For a while it was known that the 168 bit variant had an attack that reduced its effective key size to 112 bits, so a lot of people just went with the 112 bit variant. Now we know that the 112 bit variant is vulnerable to a different attack, giving it an effective key size of 80 bits, but that's another story. – Major Major Jun 16 '13 at 01:06
2

Regarding your question about 64 bits being now less secure than 128 bits: with every increase in processing power it takes less time to crack it using brute force. This article gives a good reference for the time it takes to brute force a key:

http://tjscott.net/crypto/64bitcrack.htm

The article assumes 2 Pentium 3.2 GHz processors to do the job. Processor capacity increases all the time and we are likely not too far away from 64 core and even 256 core commercially available processors.

Todd Dill
  • 181
  • 5
  • I would also like to add that time needed to crack a password decreases A LOT when using a modern GPU to do the computing work. –  Jun 08 '12 at 06:56