Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Thread: 8 bit CPU cipher

  1. #1
    dion
    Guest

    8 bit CPU cipher

    i want to make a dongle like protection with 8 bit CPU (which also known as smart card CPUs), with 8K ROM and 256 bytes RAM.

    it gonna encrypt a file with a key. the cipher kind come to my mind is block cipher. i've read the new AES candidate paper. and those who suitable with that spec are:

    Crypton, DEAL, DFC, Magenta, Mars, RC6, Rijndael, SAFER+, Serpent, and Twofish.

    could anyone tell me which one of these is the best to implement and for security ?
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  2. #2
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    Those were the ones submitted as candidates; Serpent, Twofish, Rijndael, RC6, and MARS amde it to the final round. Some pretty hefty attacks were levied against RC6 and MARS. Rijndael won, and since it's byte-based, it works well on 8-bit processors. It's very easy to understand; I'd suggest you use that one.

    You should be aware of attacks against smartcard chips, like power analysis, and fault analysis. How is the system going to be used?

  3. #3
    dion
    Guest
    the system is dongle like, it transfer an encrypted file purchased, and there's timestamp too, if needed. about power/some else analysis, i'm not look at those thing yet.

    yeah, after search and read some, the winner is Rijndael, and i read from somewhere that it has 8051 implementation, which is an 8 bit cheap microprosesor. but i couldn't find it. Could u tell me where's the good resource for this thing, Mike ?
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  4. #4
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    You can write the author at vincent.rijmen@esat.kuleuven.ac.be or post on sci.crypt.

  5. #5
    dion
    Guest
    thanks... i waiting for reply now.
    and how about the security problem, Mike ?
    there's several cryptanalysis out there about rijndael. do i have to take care of it ?
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  6. #6
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    Right now (as far as I know) the paper I co-wrote as part of the extended Twofish team is still the best attack against rijndael. It does not come close to breaking it.

  7. #7
    dion
    Guest
    now on reading rijndael algo...
    the preliminary math is finite field GF(2^8). but, sadly, i don't know much about it. could you tell me where's the good resource to learn this thing ?

    and meanwhile, i'll be off for a week, just for a moment, while still reading rijndael aes proposal.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  8. #8
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    GF(2^8) is a field; that is, you can do addition & multiplication, and every element except zero has a multiplicative inverse. That is, for every element x except zero, there's an element y such that x*y=1.

    GF(p^n) behaves like polynomials of order (n-1) with integer coefficients mod p. So in this case, addition acts like XOR. The polynomials are also taken mod a "primitive polynomial". I won't give the defenition here; if you're interested, I'm sure you can find it somewhere on the web.

    So for example, say our primitive polynomial is x^4-x-1.

    Starting with 1 and multiplying by x, we get

    1 = 1
    x = 2
    x^2 = 4
    x^3 = 8

    and then we get to x^4. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

    x^4 = x+1 = 3
    x^5 = x^2+x = 6
    x^6 = x^3+x^2 = 12

    and then we get to x^4+x^3. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

    x^7 = x^3+x+1 = 11

    and then we get to x^4+x^2+x. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

    x^8 = x^2+2x+1 = x^2+1 mod 2 = 5
    x^9 = x^3+x = 10

    and then we get to x^4+x^2. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

    x^10 = x^2+x+1 = 7
    x^11 = x^3+x^2+x = 14

    and then we get to x^4+x^3+x^2. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

    x^12 = x^3+x^2+x+1 = 15

    and then we get to x^4+x^3+x^2+x. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

    x^13 = x^3+x^2+2x+1 = x^3+x^2+1 mod 2 = 13

    and then we get to x^4+x^3+x. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

    x^14 = x^3+2x+1 = x^3+1 mod 2 = 9

    and then we get to x^4+x. We take x^4 modulo x^4-x-1 and get x+1. Then we multiply by x again until we get an x^4 term:

    x^15 = 2x+1 = 1

    which is where we started.

    We can do this whole thing easier by shifting left one bit and if the carry bit (bit 4 in this case) is set, XOR with 3. Notice that we got every number between 1 and 15 and that x^15 = 1.

    So, for example, x^13*x^2 = 1 = 13*4. So 13 and 4 are inverses in GF(16).

    Hope that quick review helps.

  9. #9
    dion
    Guest
    welcome back again.
    Hi, Mike, thanks for that review, if i'm not wrong, you're trying to figure out how primitive polynomial in GF(2^8) works. that's good, but i had it mine now. hmm... is that true that multiplicative inverses can be calculated with bit shift in 4 bit form ? is it not in 8 bit form ?

    i've read whole proposal, but can't take it at once. and well, the real source code for 8 bit processor is in C language, and implemented by C51 software simulator. but, i think it won't help me to learn the algo more than assembly language in 8051. is there anyone has implement it in assembly 51?
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  10. #10
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    I was illustrating gf(16) modulo x^4-x-1. You would be using gf(2^8) modulo something else (doesn't really matter what, since they're all related by linear transformations).

    Rijndael goes like this

    key xor
    sbox
    shift
    mix

    repeated 16x and one more key xor.

    Sbox replaces every byte x by s(x). Shift moves bytes around on a row. Mix is a matrix multiplication in GF(2^8).
    Last edited by mike; June 18th, 2002 at 15:09.

  11. #11
    dion
    Guest
    author said that he choose a polynom such that it has inverse form. umm... how can one determine such polynom has an inverse, and how to do the calculation ?
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  12. #12
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    The polynomial has to be primitive in the field. For example, with 5 bits, taking the polynomials modulo x+1 doesn't give rise to a field--2 isn't a generator. There's no number y such that 7=2^y, for example.

    I don't know offhand what the algorithm is to find primitive polynomials, but there are tables of them for small integers.

    As far as I know, they just chose the first one they found for 8 bits out of a table that used some standard ordering.

    All of this is irrelevant for implementation issues. It's only useful if you're going to be cryptanalyzing it. (By all means, do!)

    The C reference implementation is very readable. I recommend that you look it over.

    Did you know about aes.nist.gov that has everything anyone has ever written about AES?

  13. #13
    dion
    Guest
    i've read the C source code, and i've download all paper about rijndael from nist. alas, as far as i know, the C51 code is little diff from conventional C code, but i don't see that in their C source code.

    hmm.. so there's a table. and yep! i am willing to cryptanalyze it! but i'm lake understanding in this field, so that i'm asking in this forum.

    honestly, i still don't fully understood your exp about primitive polynom, Mike. but, the means of all is there's an inverse form. by now i'm trying to explore this. is the heart of this polynom is somekind of modulo ?
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  14. #14
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    First go find a good intro to number theory that talks about finite fields. These are also known as Galois (pronounced "gal-wah")fields, thus the GF(.) notation.

    A field has commutatitive multiplication and addition defined, and every element except zero has a multiplicative inverse. I think that's what they were talking about when they mentioned inverses. The s-box is written concisely as inv(x) XOR 99h, where inv(0)=0.

    The key XOR step is just addition in GF(256)
    The sbox is inverse followed by addition
    the shift is just moving bytes around
    the mix is matrix multiplication

    You already know all these concepts except how they work in gf(256), so go find a tutorial on it.

    If things look a little different in different implementations, it's because they've implemented different optimizations. There's a whole section on them in the NIST proposal.

  15. #15
    dion
    Guest
    umm... could you recommend me one of them, i mean good intro to finite field.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

Similar Threads

  1. a simple substitution cipher or not?
    By dion in forum RCE Cryptographics
    Replies: 3
    Last Post: February 27th, 2010, 10:11
  2. WinZip cipher
    By naides in forum RCE Cryptographics
    Replies: 43
    Last Post: November 1st, 2006, 16:21
  3. stream cipher???
    By crUsAdEr in forum RCE Cryptographics
    Replies: 28
    Last Post: March 27th, 2002, 23:20

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •