UNBROKEN BLOCKS
     
Author: Alexis Warner Machado
EMail : alexis.machado@task.com.br; alexis.machado@telemigcelular.com.br 

1) Introduction
   
   I present here the "Caligo" block cipher.
   
   Besides simplicity, two noteworthy characteristics is

   a) There is no restriction on the block size. The block could 
      have the common 128 or 256 bits, but also 1 or 2 bits, or
      the size of a hard disk sector.

   b) All operations are done on whole blocks. They are not divided
      for s-box or Feistel transformations.

   So, if we are trying to find some statistical property of the
   256-bit version, why not perform an exaustive search on the
   16-bit version and verify or proof this property on the higher one ?
   Using this approach I describe in section 5 my initial attempt 
   to investigate the cipher differential "behavior".


2) Encryption

   The encryption round functions u_i are defined by
   
      u_i(X) = K[i] * (X ^ K[r+i] + K[2r+i])" (mod 2**n)  (i = 0..r-1)
   
   where
   a) n is the block size in bits.
   b) r is the number of rounds.
   c) Operator ** is exponentiation.
   d) Operators * and + are modular multiplication and addition (mod 2**n).
   e) Operator ^ is the bitwise xor of two blocks.
   f) Operator " is the bit reversal of a block. Multiplication combined with
      bit-reversal provides diffusion for the cipher. 
   g) X is the n-bit block to be encrypted.
   h) The subkey K is a vector of 4r blocks. The first r blocks, K[i], are 
      odd integers. The last r blocks are multiplicative inverses (mod 2**n) 
      of the first r ones, which must be odd.

   Encryption is done by composing the round functions :

      f(K, X) = u_r-1 o u_r-2 o ... o u_0 (X)

   where 'o' is the function composition operator. 

3) Decryption

   Decryption round functions:

      v_i(X) = ((X * K[3r+i])" - K[2r+i]) ^ K[r+i] (mod 2**n)  (i = 0..r-1)
   
   Decryption function:

      g(K, X) = v_0 o v_1 o ... o v_r-1 (X)


4) Subkey Setup

   The master key M is a vector of m blocks: (M[0], M[1], ..., M[m-1]). 
   The first 3r blocks of the subkey K are (recursively) derived from M by 

      K_i+1 = ( f(K_i, M[i]^C[0]) | 1, ..., f(K_i, M[i]^C[ r-1]) | 1, 
                f(K_i, M[i]^C[r])    , ..., f(K_i, M[i]^C[3r-1]) )    (i = 0..m)

   where
   a) M[m] = 0
   b) C and K_0 are fixed vectors, formed by (pseudo) random generated 
      blocks (see Appendix A).
   c) The 'or' with 1 ('| 1') forces the first r blocks to be odd
   d) K = K_m+1 is the subkey used for encryption
    
   After aplying this formula, the last r blocks of K (K[3r]..K[4r-1]) 
   are calculated as multiplicative inverses of the first r blocks 
   (K[0]..K[r-1]).


5) Differential Properties

   All possible 16-bit input blocks and input differentials U was used 
   to get the occurrence count of all output differentials V with varying 
   master key (M) and number of rounds (r). V is given by

      V = f(K, X) ^ f(K, X ^ U) 

   For a round function without modular addition, the differentials 
   U = V = 2**15 - 2 (0111...1110) was found to be the best pair. 
   This V occurrs for half of the input blocks when r = 1, i.e., 
   probability 1/2 for a single round. For a n-bit block, we will 
   see that U = V = 2**n - 2 also works. This differentials was 
   already found (ref [1]) by analytical ways (I think).

   With modular addition, the above probability vanishes (ref [2]
   predicts 1 / 2**(n-2)). More interesting, the distribution of V 
   flattens fast as the number of rounds increases, but stops at 
   round 6 with a maximum of 24 ocurrences (see tables below). Its 
   reasonable to conjecture that, on higher bit-size versions, we 
   gain no additional protection against differential cryptanalysis 
   with more than 6 rounds. 

   This table shows the most frequent output differentials (V_max) 
   when modular addition is removed:

   Rounds  M_max   U_max   V_max   V_max ocurrence
   ------  ------  ------  ------  ---------------
    1      0x0000  0x0001  0x8000  0x10000
    2      0x0000  0x7FFE  0x7FFE  0x4000
    3      0x0000  0x7FFE  0x7FFE  0x2002
    4      0x0003  0x7FFE  0x7FFE  0x1040
    5      0x0001  0x7FFE  0x7FFE  0x086E
    6      0x0001  0x7FFE  0x7FFE  0x0438
    7      0x0003  0x7FFE  0x7FFE  0x01F8
    8      0x0000  0x7FFE  0x7FFE  0x00F2
    9      0x0000  0x7FFE  0x7FFE  0x008C
   10      0x0001  0x7FFE  0x7FFE  0x0050

   Note the different distribution for complete round functions :

   Rounds  M_max   U_max   V_max   V_max ocurrence
   ------  ------  ------  ------  ---------------
    1      0x0003  0x0001  0x8000  0x10000
    2      0x0069  0x0001  0xC001  0x8000
    3      0x0069  0x0005  0x1000  0x165E
    4      0x0021  0x0001  0x8000  0x01EC
    5      0x0021  0x0001  0x204B  0x002C
    6      0x000D  0xCAF9  0x1B1B  0x0016
    7      0x003A  0x1822  0x7456  0x0016
    8      0x0005  0xF1F6  0x7DD3  0x0016
    9      0x0099  0x67C0  0xCD31  0x0018
   10      0x001E  0x2AB1  0x6FC2  0x0016

   My main interest now is to formalize and give some proofs for 
   this "conservation of properties" on different block sizes. 
   Ideas are welcome !


6) Performance

   To be competitive, this algorithm needs a processor with fast 64-bit 
   multiplication like Alpha 21264, Itanium or Athlon64. Below is a 
   comparision with Rijndael running on Alpha 21264 (see ref [3]).   

   Cipher   KeySize Rounds BlockSize Cycles/Byte Observations
   -------- ------- ------ --------- ----------- -----------------------------
   Rijndael 128     10     128       18           
   Caligo   -        6     256       21          Key size doesn't affect encrypt velocity
   Caligo   -        6     128       22           
   Rijndael 256     14     128       25          My estimation of Cycles/Byte


7) References

   [1] Furman, V. "Differential Cryptanalysis of Nimbus"
       Fast Software Encryption: 8th International Workshop

   [2] Machado, A. "Differential Probability of Modular Addition with a 
       Constant Operand" http://eprint.iacr.org/2001/052

   [3] Weiss, R. and Binkert, N. "A comparison of AES candidates on the Alpha 21264" 
       http://csrc.nist.gov/encryption/aes/round2/conf3/papers/18-rweiss.pdf


Appendix A) Fixed Vector Calculation

   The following function fills the blocks of a vector with 32-bit words 
   produced by a "multiply with carry generator" (mwcg). The pseudo-language 
   accepts integers of any bit size.
      
      typedef unsigned int(n) block  /* n-bit integer */
      typedef block vector[3*r]
      typedef unsigned int(64) uint64  
  
      vector FixedVector (uint64 a, boolean ForceOdds)
      {
        uint64 x = 1, mask = 0xFFFFFFFF;
        block B;  vector V;   

        for i = 0 to 3r-1 do {
           V[i] = 0
           for j = 0 to (n-1)/32 do {
              x = a * (x & mask) + (x >> 32)  /* mwcg */
              B = x & mask
              V[i] += B << (j * 32)  /* overflow discarded */ 
           }
        }
        
        if (ForceOdds)
           for i = 0 to r-1 do V[i] |= 1  /* First r blocks odd */ 

        return V;
      }

   To calculate the fixed vectors of section 4 do
      
      C   = FixedVector (0x7F13AC69, False)
      K_0 = FixedVector (0x6AC690C5, True )


Appendix B) Test Vectors
   
   Block size        (n): 64 bits
   Master key blocks (m): 2
   Number of rounds  (r): 6
   
   Master key (hex dump):
     000102030405060708090A0B0C0D0E0F
   
   Derived Subkey (blocks shown as hex integers)
   Multiplicative blocks:
     K[00] = 0x13F772316E7911C5
     K[01] = 0xF10B012D68A7C1F9
     K[02] = 0xC8E620314516EF49
     K[03] = 0x356D58EB385099F7
     K[04] = 0x6C0AB242AE7719A7
     K[05] = 0xD5A2A3FAE85F3D27
   Xor blocks:
     K[06] = 0x8C128626DBA7E796
     K[07] = 0x7F96B0BE0B009683
     K[08] = 0x70B57396C559478A
     K[09] = 0x3F1D1C03BCE24437
     K[10] = 0x72C0760F5C8B16B4
     K[11] = 0x202FCF028A75BE82
   Additive blocks:
     K[12] = 0x9A933BE0B2A4888F
     K[13] = 0xC3F6E85385F67FF0
     K[14] = 0x6B74EB945C3BB223
     K[15] = 0x453D3B4AF0C8DC5B
     K[16] = 0x7277F2B3C8A27F7F
     K[17] = 0x01D1C8E98F8FDD00
   Multiplicative inverse blocks:
     K[18] = 0xCFCBF8962AD0450D
     K[19] = 0x0F7D8FFF54E33049
     K[20] = 0x8F36B6EF914D32F9
     K[21] = 0x94C01E10A6CDF7C7
     K[22] = 0xE4DEA10BE27FFE17
     K[23] = 0x894AE7B4C8866297
   
   Original block   Encrypted block   (hex dump)
   0000000000000000 04D120DD9AF18C86
   0100000000000000 CFD7F081A0C0708B
   0200000000000000 3CDC51474BB2082B
   0300000000000000 B805D330F468997C
   0000000000000001 B75CABB31234BE07
   0000000000000002 BB4C8643315E2380
   0000000000000003 A31A54065A35B287
   0001020304050607 7FF33CC0593B2BA2
   0706050403020100 84F35D9DC45BB6E7


   Block size        (n): 128 bits
   Master key blocks (m): 2
   Number of rounds  (r): 6
   
   Master key (hex dump):
     000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F
   
   Derived Subkey (blocks shown as hex integer)
     Multiplicative blocks:
     K[00] = 0x8C7F6FDEA3A8796CFE9D6FDBAA5D34B9
     K[01] = 0xD6FCFBF58FF7BB0DE28437D653D45ACD
     K[02] = 0xD7F865EC658E480096C673110F9B1B0B
     K[03] = 0x1BFF7A1F22F4DEA2798BDF7622D727FB
     K[04] = 0xF32DEEA0AA717B66FFB455212F72A095
     K[05] = 0x20FDEF35DF9B22EA0E4EB5596E9D9A71
     Xor blocks:
     K[06] = 0x86D85F3D271E001A293B982DCCDCF149
     K[07] = 0xE23E77392F1ECCCA8CB98281F554D238
     K[08] = 0xCEF0FF5031E5FEC7F2F6B0682C13B664
     K[09] = 0xA72DFB2DF029F1080C1DFE78F6353513
     K[10] = 0x114C908C376BDE0087CDF5A4CDF64EDD
     K[11] = 0x73B92A893BFD920A49ABDC0EFD3C1BA0
     Additive blocks:
     K[12] = 0x887CDD18598A91E76C50CDD97EC5A6DE
     K[13] = 0x682648FCA0DA8F80C4AB1136952B56F6
     K[14] = 0x4B2E4FD223694F392C7FBA8597E4B1AB
     K[15] = 0x62FF7A16644567C863A06D823EA082D0
     K[16] = 0xDDB14C3FA1A677B2A57DC421C74DB03B
     K[17] = 0x03D6DDDD8D7DF6DD3C1285A6E97025CB
     Multiplicative inverse blocks:
     K[18] = 0x86D9BCD7036D3B6B71E73C7256529189
     K[19] = 0x5FF64FB94D9113B018DFC0AEC1F72205
     K[20] = 0x5DB19EA04E220F4B96918257C41658A3
     K[21] = 0x0E3BE1075FA92BA4189DA409D11DCB33
     K[22] = 0x79FC8F071EA8E5988B77C24C2D2B2ABD
     K[23] = 0xD8DF3FB6D19BB9721E1C76A1589AE691
   
   Original block (hex dump)        Encrypted block (hex dump)
   00000000000000000000000000000000 63121E79517F3CB21533333657625364
   01000000000000000000000000000000 E9B93BC0D0387AD8914C406C6C4BFAEF
   02000000000000000000000000000000 59EE13CA6883FDA97193288865980555
   03000000000000000000000000000000 738ED3DD4C347B5278A0D4A53742F8F9
   00000000000000000000000000000001 5686E2CF12D6350E617F19D4390E6BB8
   00000000000000000000000000000002 C84A4D7F25C7DB0C7D50EF37BCCE5673
   00000000000000000000000000000003 2B9271A8458E5DC31CADA3D4BA3CFDCB
   000102030405060708090A0B0C0D0E0F 9AA802DC92AE8DBDBE4A75414D249040
   0F0E0D0C0B0A09080706050403020100 485B455A0BE218866D14070DED9823C5


   Block size        (n): 256 bits
   Master key blocks (m): 1
   Number of rounds  (r): 6
   
   Master key (hex dump):
     000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F
   
   Derived Subkey (formed by 256-bit blocks shown as hex integer)
     Multiplicative blocks:
     K[00] = 0x0337AB1DD12C6C84144FF81D3620ADEF028C6CB9B40FA3CD323F439239C5355B
     K[01] = 0xC219C26B7CD32CB324B8EEC01F23A572786DC05F1C0E6BF1E9DF5FC5763C4BE9
     K[02] = 0x1AB4E354716193302C88ADD6700C550D47DE765EACFE1541090190AF45F8E961
     K[03] = 0xB564D34273B2FC9521A2D41B1620B8501528FAA2E393C69294D4CACDF19525C5
     K[04] = 0x998BD63AAECA8DEE649711B3D281B34A38ADF8B46BF01AB7E95484F5674FBC09
     K[05] = 0x141561DC5F696C229C196BABDA9039C993F691DCC3E34F69124BDFCD3937C1DF
     Xor blocks:
     K[06] = 0x8CDEA5DC2164D3EE25F3DDA13E2D33FFFFCA3F185D197DA1245B8ED3C5D55E9C
     K[07] = 0x5A8BAD7BB11C7A351DE2C9F512635A61A99B00323F0B54944DFD5857A4E40B3D
     K[08] = 0x051CA73101139DD51AA54B7B70FA5ACAFCAF42408593F45DC1B43F863D8FE751
     K[09] = 0xD89DA36A246D486D1D6AEDEF5C60F1EF1EF274162DFA36BBB0051C221DD4B6B4
     K[10] = 0x7F24BDCAB501DAE3F047A027C229ADCF13DA2FF2AD3AF4DC64B387ADC88A4AE2
     K[11] = 0x0B942E37526CD3F7081E005FA72366D959899A95E61B596BC55954F7AE4519F8
     Additive blocks:
     K[12] = 0x148582FAA197A95C629D4191CB9879268AE4FA2F823A259D68561CCDEA4C9869
     K[13] = 0xCA3C47EED2E61642B53736CD5C89CB01462F725A852DDE8FC9786251A7B26614
     K[14] = 0x0FADF5289F220F8B3B9F1BDE9E4DE2F7000226BA46F5A172DFF35EE7078CD965
     K[15] = 0x1909A84618890E065684C4D5106C5319BC2D97D2F509A3CB5F8CE50B21E4BACC
     K[16] = 0xED7B085BAEFA3194EA543AF78682306272E02B480363C0BBB14ABEC51F958C9B
     K[17] = 0xB49B9949E9473788C9C30870C8BCE0FCF9CE9DC5126E1E68ED80C88B4B14DBFB
     Multiplicative inverse blocks:
     K[18] = 0x5F600B0AFAF8A22A43CF829DA03EF9148D474C24C39D2279DF2D7D1D801FF2D3
     K[19] = 0x31B7CC32AA90EB1AF70D3FB018A0048C786D67098DE204E17C08B08AA4E73C59
     K[20] = 0xC73E8E84418054A95A54DA2E1C9DF8235266C013EB843900F79E17B3F75D7AA1
     K[21] = 0xF53923F5E925588E8E7BA3E39EFEBDBBF89BEA2BB0B013D2101B08F55DEF110D
     K[22] = 0x3E0682D114AFB49598C6FA25ACC57DF332DAF7365980679895F8D65EFA729239
     K[23] = 0x0C0130D67E3C98F91AEA2F68CD31978B555296656263524FE374AA68680D3A1F
   
   Original block (hex dump)                                        Encrypted block (hex dump)
   0000000000000000000000000000000000000000000000000000000000000000 2B55A0B143ADF104C6036E708AFB435988A6CDDA948C0BB252C8725C91E6D292
   0100000000000000000000000000000000000000000000000000000000000000 4DE87EE62CC476AC1772F7489D50F20959B4993F795AA4F09609E37D313B40FD
   0200000000000000000000000000000000000000000000000000000000000000 7939CE0B25ACD72A1F66CB19F859DE00F65F56180057B691C175A73A08B6CF66
   0300000000000000000000000000000000000000000000000000000000000000 AC0B0BAE091E28509732930D51A5B3C8B3126CB3C21E8F808E080466FE69AF2C
   0000000000000000000000000000000000000000000000000000000000000001 D7E84F2862911DAB9AC9859936B2A206D16F4EFC804D4FA8CAB413C6DC507FDB
   0000000000000000000000000000000000000000000000000000000000000002 E2A96767DC2183D762AC80424C8778E3C52C2DF5734F92295AE3945B6EBAF9AE
   0000000000000000000000000000000000000000000000000000000000000003 10835E77EB48B14A82CE93F73AF683B18FFA2608498245F2D1DF9463E74C7C10
   000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F 3E7A7C6CC3B627A1AB54A28FF26D307C94D30B0ECD5F99B21B5BD49755867015
   1F1E1D1C1B1A191817161514131211100F0E0D0C0B0A09080706050403020100 692BA6AB59CA1FFEFF870E959ED1A1A8C2DB0F0B484B1E1F4EF836FD2F5346BC