7
votes
$\begingroup$

The first step In Algebraic-attack is expressing the cipher operations as a system of equations. Is there an automated tool to do this?

$\endgroup$
  • 1
    $\begingroup$ Part of the "art" of algebraic attacks is finding the appropriate field to embed the operations into. I would suspect if an automated tool were to be implemented (none to my knowledge), it wouldn't be very useful at finding "nice" representations. For example with AES, some operations are cleanly representable in GF(2) while others in GF(2^8). You can embed everything into GF(2^8) (e.g, big encryption scheme BES) but the representation gets messy. $\endgroup$ – PulpSpy Jul 14 '11 at 15:07
6
votes
$\begingroup$

Theoretically, the equations could be derived from the representation of the cipher in a hardware description language like VHDL or Verilog; you implement the cipher as if you want to make a FPGA/ASIC which runs it, but you stop at the symbolic representation of the logic gates (the "netlist"). However, I am not aware of any existing conversion tool which will transform a netlist into a sequence of equations in the right format for whatever equation solver you want to use for performing the attack.

$\endgroup$
0
votes
$\begingroup$

Yes, there is an automated tool exists for stream ciphers, and is easily configurable for new ones: https://github.com/msoos/grainofsalt by Mate Soos (great guy, creator of CryptoMiniSAT)

Otherwise, manually but software assisted, people use often Sage for this using this function: https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/boolean_function.html#sage.crypto.boolean_function.BooleanFunction.algebraic_normal_form and then ANF2CNF by Sage author Martin Albrecht: https://doc.sagemath.org/html/en/reference/sat/sage/sat/converters/polybori.html

CryptoMiniSat (and many other SAT Solvers) "eat" CNF as input.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.