OKlibrary  0.2.1.6
general.hpp File Reference

On investigations into KeeLoq cipher. More...

Go to the source code of this file.

## Detailed Description

On investigations into KeeLoq cipher.

Todo:
Overview
• KeeLoq is a 528-round iterated shift-register cipher with 32-bit plaintext, and ciphertext, and 64-bit keys.
• The KeeLoq encryption cipher consists of the following:
• A key point here is that the KeeLoq round function is the combination of a small XXX and the XOR of X more bits, meaning that the entire round function is a XX bit boolean function.
• Algebraic attacks using SAT solvers are discussed in [Algebraic and Slide Attacks on KeeLoq; Bard, Courtois, Wagner 2008], theoretically breaking the cipher in time equivalent to 2^53 encryptions, compared to 2^64 for brute-force.
Todo:
Analysing the KeeLoq round function
• The KeeLoq round function is given as a boolean function by the Maxima function keeloq_round_bf in Cryptology/Lisp/CryptoSystems/DataEncryptionStandard/Cipher.mac.
• Computing statistics:
```maxima> Round_DNF : bf2fulldnf_fcl(keeloq_round_bf,9)\$
maxima> statistics_fcs(Round_DNF);
[9,256,2304,9,9]

maxima> Round_CNF : bf2fullcnf_fcl(keeloq_round_bf,9)\$
maxima> statistics_fcs(Round_CNF);
[9,256,2304,9,9]

maxima> output_fcs("KeeLoq Round Function", Round_CNF, "KeeLoq_Round_full.cnf")\$

shell> QuineMcCluskeySubsumptionHypergraphWithFullStatistics-n16-O3-DNDEBUG KeeLoq_Round_full.cnf > KeeLoq_Round_full.cnf_shg
shell> cat KeeLoq_Round_full.cnf_primes_stats
pn      pc      n    nmi       c        l     n0   n0mi      c0       l0  cmts
9     224      9      9     224     1760     NA     NA     224     1760     0
length   count
7      32
8     192
shell> cat KeeLoq_Round_full.cnf_shg_stats
pn      pc      n    nmi       c        l     n0   n0mi      c0       l0  cmts
224     256    224    224     256      512     NA     NA     256      512     0
length   count
2     256

shell> \${OKplatform}/OKlib/Satisfiability/Optimisation/minimise_cnf_cryptominisat KeeLoq_Round_full.cnf > KeeLoq_Round_min.cnf
shell> cat KeeLoq_Round_min.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG
pn      pc      n    nmi       c        l     n0   n0mi      c0       l0  cmts
9      96      9      9      96      736     NA     NA      96      736     1
length   count
7      32
8      64

maxima> Round_primes : read_fcl_f("KeeLoq_Round_full.cnf_primes")\$
maxima> Round_min : read_fcl_f("KeeLoq_Round_min.cnf")\$
maxima> hardness_wpi_cs(setify(Round_min[2]), setify(Round_primes[2]));
1
```
So the minimum representation has hardness 1!
• Investigating the ANF to CNF encoding for the KeeLoq round used in [Algebraic and Slide Attacks on KeeLoq; Bard, Courtois, Wagner 2008]:
``` /* Generating the encoding: */
maxima> Round_anf : lappend(map(lambda([v,C], cons(adjoin(v,map("-",C)),create_list({-v,l},l,listify(C)))),[10,11,12,13,14,15,16,17,18,19,20],[{4,6},{4,8},{5,6},{5,8},{6,7},{7,8},{11,7},{11,6},{20,7},{20,6},{4,5}]))\$
maxima> Round_par_anf : append(
fullxoreqs_wv_fcl(4,1,[1,2,3,7,21])[2],
fullxoreqs_wv_fcl(4,1,[8,10,11,12,22])[2],
fullxoreqs_wv_fcl(4,1,[13,14,15,16,23])[2],
fullxoreqs(3,1,[17,18,19,24])[2],
fullxoreqs_wv_fcl(4,1,[21,22,23,24,9])[2]);
XXX Apparently each fullxoreqs_wv_fcl(m,1,L) just expresses that the first
variable in L is equal to all the others ???
XXX
maxima> Round_anf : append(Round_anf,Round_par_anf);
maxima> statistics_cs(Round_anf);
[24,105,429,5,2]
/* Checking we compute the right function: */
maxima> for C in Round_CNF[2] do assert(ucp_0_cs(apply_pa_cs(comp_sl(C),setify(Round_anf))) = {{}});
done
maxima> for C in Round_DNF[2] do assert(ucp_0_cs(apply_pa_cs(C,setify(Round_anf))) = {});
done
/* Computing a lower-bound on the hardness, the hardness w.r.t the prime
implicates on the original variables: */
maxima> hardness_wpi_cs(setify(NLF_nv), setify(Round_primes[2]));
2
```
So the ANF representation used has a higher hardness, and is also a larger representation. The minimum 1-base above should be a much better representation of the KeeLoq round function.
• KeeLoq should be implemented at the Maxima level, and then translated, so that we can compare these translations.

Definition in file general.hpp.