Tag Info

Hot answers tagged

42

In the first decade of the 21th century, and counting, on a given $Year$, no RSA key bigger than $(Year-2000)\cdot 32+512$ bits has been openly factored other than by exploitation of a flaw of the key generator. This linear estimate of academic factoring progress should be used neither for long-term predictions (after 2016 or 1024-bits) nor for choosing a ...


34

For practical purposes, 128-bit keys are sufficient to ensure security. The larger key sizes exist mostly to satisfy some US military regulations which call for the existence of several distinct "security levels", regardless of whether breaking the lowest level is already far beyond existing technology. The larger key sizes imply some CPU overhead (+20% for ...


20

The actual encryption algorithm is almost the same between all variants of AES. They all take a 128-bit block and apply a sequence of identical "rounds", each of which consists of some linear and non-linear shuffling steps. Between the rounds, a round key is applied (by XOR), also before the first and after the last round. The differences are: The longer ...


15

You might want to look at NIST SP800-57, section 5.2. As of 2011, new RSA keys generated by unclassified applications used by the U.S. Federal Government, should have a moduli of at least bit size 2048, equivalent to 112 bits of security. If you are not asking on behalf of the U.S. Federal Government, or a supplier of unclassified software applications to ...


14

Computational cost of RSA with keys of length $n$ bits is roughly $O(n^2)$ for public key operations (encryption, signature verification), and $O(n^3)$ for private key operations (decryption, signature generation). So RSA with a million-bit key will be roughly one billion times slower than RSA with 1024-bit keys (for the private key operations); the latter ...


13

First of all, I'm no expert in this area. Generally $n$ bit ECC seems to have a security level of about $n/2$, but I found some claims that it's lower for certain types of curves. RFC4492 - Elliptic Curve Cryptography (ECC) Cipher Suites contains the following table: for Transport Layer Security (TLS) Symmetric | ECC ...


13

That's not the same kind of key. Symmetric keys are bunch of bits, such that any sequence of bits of the right size is a possible keys. Such keys are subject to brute force attacks, with cost $2^n$ for a $n$-bit key. 128 bits are way beyond that which is brute-forceable today (and tomorrow as well). If a block cipher is "perfect" then enumerating all ...


11

Those appear to be based on the complexity of the General Number Field Sieve, one of the fastest (if not the fastest) classical factoring algorithms. I confirmed this in Mathematica. Here is the complexity for the GNFS (pulled from the linked Wikipedia article): $$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln ...


9

Symmetric encryption and asymmetric encryption algorithms are built upon vastly different mathematical constructs. In typical symmetric encryption algorithms, the key is quite literally just a random number in $\left[0 .. 2^n\right]$, where $n$ is the key length. The strength of the key is based upon its resistance to brute-force attacks, where an attacker ...


9

In RSA, the bit size $n$ of the public modulus $N$ is often of the form $n=c\cdot2^k$ with $c$ a small odd integer. $c=1$ ($n=512$, $1024$, $2048$, $4096$.. bit) is most common, but $c=3$ ($n=768$, $1536$, $3072$.. bit) and $c=5$ ($n=1280$..) are common. One reason for this is simply to limit the number of possibilities, and similar progressions are found ...


8

Oh, and while you did not specifically ask about this, there is another point I believe that is important to highlight; DH and SRP are different protocols, and have different requirements on the generator they use. In particular, taking a generator that is designed to be used securely within DH can void the security properties of SRP. Here's what's going ...


8

Well, yes, that is generally good advice about DH. Here is some background on this: support you were given a value $g^x \bmod p$, and you were also told that $1 \le x \le A$ for some value $A$. If so, then there are several known attacks (such as Big Step/Little Step and Pollard's Rho) that can recover $x$ in about $\sqrt A$ steps. If we have as our ...


8

Presumably, it's because they rounded it down to a nice round number of bits. Nobody's going to use an 86.76611925028119 bit key in practice, but an 80-bit key is plausible. Besides, the 86.whatever bit symmetric key length is only approximate, anyway: even using the GNFS, implementation details could easily swing it several bits either way, and of course, ...


7

First of all, this is not legal advice. However, I've been in the unfortunate position where I've had to deal with this legal nightmare. The new agreement which regulates export of cryptography internationally is called the Wassenaar Arrangement. If your product is what is called a mass market product, i.e available for purchase to the general public without ...


7

When they say they are using a 128 bit AES key, they mean the length of the key is 128 bits. Technically a 128 bit AES key could have 0 bits of entropy, 128 bits of entropy, or anywhere in between. To be secure, however, the 128 bit key should also have high entropy. Ideally, a 128 bit AES key would also have 128 bits of entropy. A few side notes Keep in ...


6

The difference is that all known attacks on AES [but see comments] require in the neighborhood of 2length attempts to succeed; that is, there's no better method known than simply trying different keys by brute force. It follows, then, that a 256 bit key is 2128 times as hard to crack as a 128 bit key. Of course, computing each encrypted block with 256 bit ...


6

When we consider that a Playfair key consists of the alphabet (reduced to 25 letters) spread on a 5x5 square, that's $25!$ keys (another formulation consider any string to be a key; then strings leading to the same square are equivalent keys). The rules of Playfair are such that any rotation of the lines in the square, and any rotation of its columns, lead ...


6

The fragment " what to do about padding the key ? " of the question looks scarily like transforming a password into a cryptographic key using some padding mechanism. Doing this would be a known, serious, often made and often exploited mistake. A standard security assumption for ciphers is that the key is chosen at random, and a padded password is not random ...


6

First let's take care of your encoding related issues: You can't simply say one byte equals one char. You need an encoding to transform between these, where the properties depend on that encoding. When transforming between normal text and bytes, UTF-8 is a good choice. One character will correspond to a variable amount of bytes that way. You'd use this to ...


6

A block cipher is pretty much a substitution cipher. So let's look at a simple alphabetic substitution cipher. There are 26 different plaintexts and 26 different ciphertext. The cipher is a permutation of these 26 values. But that does not mean there are 26 different permutations, it means that there are $26! \approx 2^{88.4}$ different permutations, which ...


6

No. The challenge for RSA-155 (which is 512 bits) was broken in 1999. This took 6 months on pretty advanced hardware to break at the time, which works out to 8000 MIPS years. It should be much less today. FYI, RSA 768 took just under 3 years.


6

Using powers of two is traditional. It also has a few implementation benefits for very constrained architectures: it saves a few instructions. This indirectly implies that some implementations are not able to process RSA keys whose size is not a multiple of 32 or 64, meaning that if you want maximum interoperability, you should not use other key sizes as ...


6

Yes, you can have a key of any length of that range (as long as it is an integral number of bytes), but really, why? There is absolutely no reason to. If the key is uniformly distributed, anything over 256 bits is total overkill and completely pointless. If the key is not uniformly distributed (maybe it's a passphrase or something), you should not be ...


5

I see two main points of complication: We need to find primes of appropriate size. For your "million bits" key, the primes $p$ and $q$ would have to have around 500000 bits. I suppose primality tests in this size are quite harder than for our usual 2048 bit primes (though I didn't find numbers in a quick search). Also, you would need much more entropy as ...


5

The minimum of 40 bits is conventional; below 40 bits of key material, RC4 (or practically any cipher without some built-in key stretching) is just too unsafe. At some point in history, in many countries, ciphers with a key above 40 bits where illegal in some usage (in USA: export; in France: use, sale, export); thus cipher designers wanting to prescribe ...


5

The proper way to do things in this case would be to feed the password to a key derivation function such as PBKDF2. PBKDF2 (and other KDFs) is designed specifically for what you describe. Since you are using AES-128, you would want a 128-bit output from PBKDF2, then feed that into AES. Now, stepping back a little, the best advice I can give you is to not ...


5

In my opinion, if AES-128 is broken, then it's highly likely that AES-192 and AES-256 will fall too (because these types of attacks are structural and easily extend to longer key-lengths). In fact, we know a successful attack on AES will not be via exhaustive key search on a conventional computer. There is, however, some chance that key-size will matter in ...


5

Prompted by Paŭlo's comment, I took a look at the original requirements set out for the AES candidates. A useful page for that turns out to be AES - The Early Years (1997-98) on the NIST web site (and surprisingly hard to find there; the internal links are broken and Google doesn't find it either). The AES key lengths were specified in the original Request ...


5

I imagine that Truecrypt uses a KDF, to derive a 128/192/256-bit key from your password. This is standard practice. It's unadvisable to use a password directly, as they're generally low-entropy (predictable), and too short (as you've noted).


5

I'll expand on the comment I left on my answer. The purpose of Part 2 of NIST SP 800-57 is to "[provide] guidance on policy and security planning requirements for U.S. government agencies". Keeping that in mind, the table on page 64, i.e. the table from whence the numbers in that question came, includes more than just RSA key sizes. Namely, it includes some ...



Only top voted, non community-wiki answers of a minimum length are eligible