Decryption issue with self-coded AES-128

Question

I have written my own AES-128bit implementation in Java, till yesterday I thought it would be alright. (I was working on the encryption) Now I’m trying to decrypt my encrypted cleartext, but this fails..

So, I hope I can ask such questions on here..

My Cleartext is: abcdefghijklmnop

This will be converted to the State Matrix (4x4, hexadezimal):

61 65 69 6d
62 66 6a 6e
63 67 6b 6f
64 68 6c 70

After that, it is going through the 10 rounds (The Key is generated randomly at the beginning, after that computed for every next round, will change that to a hash function later):

Round 1:

    2c d3 db c6
    3c 31 83 91
    21 a9 f5 0d
    48 9c 69 0a

Round 2:

    9f 81 b2 c8
    6e 4a 61 94
    0a b8 cb a3
    a4 4c 6c 57

Round 3:

    01 3e a4 af
    f0 69 fe 64
    1f de 19 e1
    cf a6 78 9e

Round 4:

    d0 c9 40 e5
    bd 81 de dc
    8c 5a fd e2
    61 84 37 65

Round 5:

    19 51 92 00
    63 f4 e9 33
    15 48 8e ba
    13 ae 7e 7a

Round 6:

    1e 75 41 3d
    34 ed fe 24
    f6 02 64 39
    ea 94 50 b1

Round 7:

    a9 6a 6e 8a
    7d 84 59 dd
    b3 11 f3 d2
    4d d8 e2 9c

Round 8:

    e4 c3 89 0a
    60 0a 29 e9
    91 68 2c e4
    13 23 e0 d8

Round 9:

    24 c2 1c db
    87 8c 22 bc
    0b a8 3d e9
    35 c2 3f 21

Round 10:

    a9 58 3c 76
    c0 db 39 20
    58 db 80 3d
    b6 63 b4 4e

And the KeyBlock from the beginning is:

d2 66 1b 52
08 fb 35 20
76 e9 11 1c
d3 7d 36 e0

And now, if i do the encryption backwards (with reversed tables and so on), i got this:

Round 1:

    bf 5b d2 27
    df 15 d0 d8
    a6 70 69 07
    b8 4c 4c 47

Round 2:

    89 16 66 bc
    1c 22 0e 56
    bc db f0 77
    7f b1 9e d4

Round 3:

    bf ac 65 b8
    70 70 8c a4
    ef 6b 38 cc
    63 13 ef 3e

Round 4:

    28 ba 4b bd
    44 63 d2 8c
    33 aa ab 76
    ba 71 02 00

Round 5:

    ef 45 ee b9
    fd e3 ce 09
    1a 91 de 70
    b2 95 22 2b

Round 6:

    6c 95 6a c3
    91 12 ec 27
    62 df b7 49
    ad ac 11 56

Round 7:

    8a f5 d9 c7
    68 0d be 3e
    b0 58 45 bc
    68 a1 ad b9

Round 8:

    45 11 77 dd
    84 cd f0 87
    20 06 e8 3e
    fe 32 4b e3

Round 9:

    97 77 6c 8f
    8c 36 c5 a7
    56 ef f9 22
    2d 4f 7d 03

So as you can see, there is something going on wrong.. I used this paper as main source of information (It’s in German), and I also used many other sites and Wikipedia (English Version) about Rijndael.

If someone can tell me anything with this information, that would be very very very cool, besides that I can also provide the source via email.

Answer 1

All of your encryption rounds are incorrect, either due to incorrect round function or key schedule (or state alignment). Showing round 0 (round key addition before first round) will help show if the keys are being added correctly to the state.

The key expansion is also very important, if that is not done correctly it will not work at all.

I will assume the decryption is also incorrect, but did not test, since whatever method fixes the encryption code should be applied to all code, resulting in correct outputs.

Given your plaintext and key, your state data should look as below. The key schedule values are shown as a column in 32-bit unsigned value format, which is reverse byte order from the state array:

Key schedule
Round 00  d37608d2 7de9fb66 3611351b e01c2052
Round 01  d3979464 ae7e6f02 986f5a19 78737a4b
Round 02  602b1bbc ce5574be 563a2ea7 2e4954ec
Round 03  ae1a2098 604f5426 36757a81 183c2e6d
Round 04  92b7cba1 f2f89f87 c48de506 dcb1cb6b
Round 05  ed3103ae 1fc99c29 db44792f 07f5b244
Round 06  f6f4e5b9 e93d7990 327900bf 358cb2fb
Round 07  f96281ce 105ff85e 2226f8e1 17aa4a1a
Round 08  5b922d98 4bcdd5c6 69eb2d27 7e41673d
Round 09  7c61ae06 37ac7bc0 5e4756e7 200631da
Round 10  2bd6c1f7 1c7aba37 423decd0 623bdd0a

Plaintext and initial state
6162636465666768696A6B6C6D6E6F70

  61 65 69 6d 
  62 66 6a 6e 
  63 67 6b 6f 
  64 68 6c 70 

Round 0
  b3 03 72 3f 
  6a 9d 5f 4e 
  15 8e 7a 73 
  b7 15 5a 90 

Round 1
  e6 98 e8 00 
  50 b2 f6 9e 
  ab 2f 59 ef 
  20 2a 9c 9b 

Round 2
  3d 9c 10 14 
  a9 7b e0 70 
  23 36 5a 2a 
  3d ec 58 6a 

Round 3
  09 7b 15 83 
  9e 40 b6 0c 
  7d c8 eb a1 
  5c 53 83 0f 

Round 4
  27 6f bf b1 
  8e 3e ac fe 
  ec 2d e3 b2 
  9d 79 ef d3 

Round 5
  97 a3 91 e3 
  e5 0a e3 e4 
  c7 7c b1 f5 
  cd e6 c1 20 

Round 6
  64 ec 55 c1 
  57 dd 8c 42 
  52 2d 8f ec 
  af 61 02 3f 

Round 7
  16 c2 99 a8 
  bb ce b3 80 
  99 f9 dc bb 
  64 01 d4 f2 

Round 8
  9f 92 3e 56 
  7f 4c 17 92 
  c9 8f 8b 98 
  96 25 9b c0 

Round 9
  57 83 ab a9 
  da 95 39 be 
  3c 34 5a bf 
  71 6b 7f 61 

Round 10 (final ciphertext)
  ac db b2 d9 
  eb a8 42 8a 
  68 72 d6 23 
  c4 bf 3d b0 

Ciphertext
ACEB68C4DBA872BFB242D63DD98A23B0

Answer 2

Take a look at some of the open source implementations or at the reference code. I couldn't find the later ad-hoc but some open source variants should be perfect.

I experienced similar problems. Unfortunately the byte ordering is not always that clear. As owlstead mentioned, take a look at the detailed test vectors from the NIST publication (FIPS-197, Appendix C). These include step by step results so you can check, which part of your code is wrong.