DEFCON 19 CTF FOR THE WIN!

We would like to congratulate all the members of Kryptos Logic participating in the Defcon 19 CTF with the European Nop Sled Team. This is our second year competing side by side with our great friends across the globe from Portugal to Denmark to the United States, and Kryptos Logic was honored to be a part of the fun and hard fought competition.

In t-shirt swapping tradition, Hates Irony (VedaGodz and Co), we hope to see you back next year in full force. Next year drinks on us.

Routards as usual a fantastic showing that should not go unrecognized by any team and we hope that you do return next year. Your first blood breakthroughs did not go unnoticed.

Plaid Parliament of Pwning, your first time at the Defcon CTF, and great work.

To all other teams, good luck next year

A very special note to DDTEK for organizing the "Olympics" of Capture the Flags. We think there might be the slightest bit of stress involved with running a competition where the best CTF players in the world scrutinize every line of code and gameplay. Fantastic game, good curve ball with the IPV6, and everyone worked hard until the end on both the qualifiers/finals. Affirmation, that it was a job well done.

Check our blog soon for some solutions to the qualifiers/finals.

Thanks,

Team Kryptos Logic

The sky is not falling

CRYPTO 2011's rump session yesterday was shaken by the announcement of a break of the full AES. What, again? Yes - this time AES was broken without relying on the related-key assumption. Is this any reason to panic? No.

According to the paper, the computational complexity of the attack (on AES-128) is 2^126.18. The attack requires, however, 2^88 plaintext/ciphertext pairs. What this means is that a machine of size 2^88 (the pairs must be stored somewhere) will succeed at breaking AES in 2^126 steps.

Now consider another scenario: a machine of size 2^88, with 2^88 small AES processors (admittedly, an AES circuit is a constant factor larger than a circuit to store 256 bits; the point still stands). This machine will success in bruteforcing an AES key in 2^(128-88) = 2^40 steps, much faster than the BKR attack. Perhaps now would be a good time to bring up Daniel Bernstein's paper "Understanding bruteforce," which makes the same point, but takes it even further, with a description of a parallel architecture for cost-efficient bruteforcing.

This is not, of course, to discredit the impressive research done by the BKR paper authors. This is important research, and allows us to have better insight (and attacks) into the cipher used to protect all kinds of communication around us. The authors themselves acknowledge that their results do not affect the security of AES in practice:

As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.

So the sky is not really falling. A theoretical break has been done, and it might even lead to a practical attack in the future, but not today.

Neat x86 trick

While these days it's becoming more and more of a forgotten art, bit wizardry and size coding is a fascinating subject. Many such tricks are known, and published over the decades in venues ranging from HAKMEM, to several books, to the venerable Art of Computer Programming.

In this post I show one such trick I didn't find anywhere else (although I didn't look that hard). Suppose you want to increment and decrement integers with a defined floor and ceiling; let us call those f and c. We can avoid branching by doing

sub eax, c

adc eax, c

to increment, and

sub eax, f+1

adc eax, f

to decrement. You can see that, by making clever use of the carry flag, one avoids both extra registers (as with, e.g., cmov) and branching.

Having fun with C++ metaprogramming

C++ is not a simple language. Sometimes that sucks. Sometimes we can use it to our advantange (or at least convenience).

Inspired by a recent article on compile-time string encryption, I decided to up the ante by implementing actual encryption: AES-128.

As most of you will know, the AES is composed by 4 main subroutines, which are repeated 10 times to complete the encryption of a single 16-byte block: AddRoundKey, SubBytes, ShiftRows, MixColumns.

The AddRoundKey, ShiftRows, and MixColumns subroutines mostly just shuffle and xor bytes together, thus not being any real challenge to implement. The SubBytes transformation is the trickiest to achieve, and its main component, the S-box, can be performed in two ways. The first involves specializing each template argument to the S-box for each of the 256 possible positions. The second uses the algebraic representation of the Sbox, as

S(a) = M (a^-1) + b,

where the field is F_2[x]/(x^8 + x^4 + x^3 + x + 1), M is a 8x8 F_2 matrix, and b can be represented by the 0x63 hexadecimal integers.

Once the S-box is done, it's just a matter of putting everything together and using standard looping techniques for C++ metaprogramming (feel free to read some literature, if you're not familiar).


Without further ado, here's the proof-of-concept code implementing the AES:
AES Implementation


If you're interested in more C++ metaprogramming code, check the Boost or Blitz projects; they ought to keep you busy for a while.

Hello

Welcome to our humble blog!

Here at Kryptos Logic, we deal with many different aspects of security. In this blog we'll talk about interesting projects we are working on, ranging from x86 peculiarities, binary analysis, and exploits to the state-of-the-art cryptography.

Stay tuned!

SHA-3 --- Round 3

In December of last year, the 5 SHA-3 finalists were announced by NIST's William Burr. It was only last week, however, that the official report made it out.

The five finalists are:

- BLAKE
- Keccak
- Grøstl
- JH
- Skein

The evaluation of the finalists focused on two main aspects: security (obvious) and performance. Of the 14 2nd-round candidates, none was severely broken. There were, however, some concerns raised towards CubeHash and Hamsi. The former allows for generic preimage attacks due to its narrow-pipe design; the latter allows for faster-than-theoretical second preimages.

The clear winners seemed to have been BLAKE, Keccak, JH and Skein, with pretty much no discussion of their strengths and weaknesses in the report. The last place seems to have been disputed between BMW, Grostl, CubeHash, Luffa, Fugue, and Shabal. The selection of Grostl feels like shoehorning an AES-based candidate into the finalists: it is (relatively) slow and possibly prone to cache-timing attacks.

I'm sad to see CubeHash go. I mostly agree with the author, in that it's not useful to require 2^512 preimage security, yet only 256-bit collision security --- clearly the weakest link is collision resistance, and CubeHash was pretty strong there. By the length and content of the 4.3.3 section of the report, its rejection was not a no-brainer.

Personally, I'm rooting for BLAKE. Its building blocks have been thoroughly analyzed before (ChaCha's predecessor, Salsa20, was one of the winners of the eSTREAM competition) and it has excellent performance, for which I can claim an epsilon of credit. Our SSE optimized candidate implementation can be found on NIST below.

http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Blake_FinalRnd.zip
http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/index.html
http://bench.cr.yp.to/primitives-sha3.html