What Is The Definition Of The J-invariant Of An Elliptic Curve?

What was the status of the security of RSA, elliptic curve cryptography, AES, etc. in 2013?

• Have these crytographic protocols, or any other commonly used cryptographic schemes, been proven to be secure or insecure? "Security" might be defined as, for instance, "there does not exist a better-than-brute-force way to break the scheme", and "insecurity" might be defined as "there exists a better-than-brute-force way to break the scheme". (I'm being purposefully vague; this is just one possible definition.) If no such results exist, then what are the biggest steps that have been made towards such a result?

• Answer:

  OK, let's start from the bottom.  I'll ignore implementation-specific attacks such as side channels, fault attacks etc.  Most of this information is from Wikipedia. AES There is no known significantly-faster-than-brute-force way to break AES if it is used properly.  The best measurement is therefore, how many rounds can be broken faster than brute force?  This is 7/10 for AES-128, 8/12 for AES-192, and 9/14 for AES-256, according to Wikipedia.  The reason that more rounds can be broken for stronger keys is that this is in comparison to brute force, and brute force takes longer for stronger keys. If you use keys which are related in certain ways, then there are attacks which break AES-256 faster than brute force, perhaps in as little as 2^128 time. There are also "biclique attacks", but these are probably best regarded as an optimized way to perform a brute-force attack, and they shave only a bit or so off the time required. ECC For vanilla ECC, if the curve is chosen carefully -- e.g. the NIST curves, Brainpool curves and Curve25519 -- then there is no known attack which is faster than brute force, which takes O(2^(n/2)) curve operations.  However, pairings on curves over small-characteristic fields (eg GF(2^n) and GF(3^n)) are broken by new accelerated discrete logarithm algorithms.  This doesn't apply to all binary curves, only special ones which support pairings. The biggest ECC brute force attack carried out so far was on a 112-bit prime, says Wikipedia. RSA It's not clear what "brute force" is here.  Factoring tends to be the best way to break well-designed RSA mode.  The best factorization algorithm for such numbers is the General Number Field Sieve, and it was used to factor the 768-bit RSA challenge in 2009. Discrete log For discrete logarithms modulo a safe prime, the record is 530 bits in 2007 using the Number Field Sieve.  In a 2^prime field, the record is 613 bits.  But other low- and medium-characteristic fields are worse: an attack this year solved a logarithm in 1425-bit medium-characteristic field, and another solved a logarithm in a 6168-bit binary field.  This represents significant new progress in the last few years against small- and medium-characteristic fields. Broken cipher primitives MD5 is completely broken for collisions, including chosen-prefix  collisions. SHA-0 has also been broken, with a complexity around 2^51.  SHA-1 is theoretically broken for collisions, but the attack takes about 2^63 operations and, to my knowledge, has not been performed. RC4 is somewhat broken, and attacks seem to be getting slightly better over time.  In particular, it is completely broken in WEP, and somewhat broken in SSL/TLS. CBC padding attacks against some other SSL/TLS modes are also problematic.