0
$\begingroup$

I have a 'for fun' project, which is a pure software based redesign of the Enigma I. I'd like to compute the key length of my design, but I need some help with that.

I have a write-up here (see section 1), but in summary:

  1. Conceptually it's a rotor based system, that can take any number of rotors (i.e. as set by the operator).
  2. Rotor components: stator (input/output), N number of rotors, stator (input/output). Unlike Enigma I, it has no reflector and data can be enciphered in either direction.
  3. Rotor supports 94 unique characters (A-Z, a-z, 0-9 and some special characters).

I've attempted to map out all the variables that I think contribute to the key size:

Factors that contribute to key size

In summary for those unable to see the image clearly:

  • Rotors of 94 characters
  • T - Total possible rotors (permutations of 94): 1.08736615665674E+146
  • A - rotors available for selection by the operator. Theoretically T, but practically I have an initial implementation that uses 1147 unique rotors.
  • N - the number of rotors selected by the operator. Unlike Enigma I there's no strict limit, and there's the further complication that you can use multiple instances of the same rotor (whether or not that enhances its cryptographic strength, I'm not sure).
  • O - the order in which the selected rotors can be arranged (including instances of repeated rotors). I believe the calculation for Enigma I would be 26! × (26! - 1) × (26! - 2) - which takes into account the non-reuse of rotors, which doesn't apply in this case.
  • R - starting position for rotor Rotation.
  • D - direction of rotation (forwards or reverse).
  • F - flow direction through the rotors (left-to-right or right-to-left).

Do you agree those variables all contribute to the key size (they seem to me to all be variables the operator can set, and therefore part of the key)?

Can you give me a hand to compute the key size, or point me in the right direction? I'm afraid math isn't really a strong point of mine.

Update (Re comments to Huberts answer)

Enigma I has a specific number of rotors, which reflects translates both into the key size and the size of the cryptographic problem attackers face. Calculus doesn't place a limit on the number of rotors used, which I think means that from an attacker's point of view you'd need to consider how many rotors might be being used (i.e.e a range). Where as, key size is a specific measurement of how big a specific key is.

Update (April 2018)

Project complete. Info available in the link below, including access to download (win10 only) and user guide.

https://morphological.wordpress.com/projects/enigma-x/

$\endgroup$

2 Answers 2

3
$\begingroup$

To compute bit length equivalent of your key, you need to compute $\log_2(\Omega)$ where $\Omega$ is the space of possible keys. Now, I have myself been computing the equivalent key sizes of many non-modern cryptosystems so it proved a really interesting exercise.

The formula I'm left with is

$$ \log_2(1147^N \cdot 94^N \cdot 2^N \cdot 2) $$ where $N$ is the number of rotors.

First, we select the rotors. For $N$ rotors, there are $1147^N$ possible choices. Then, we select their initial state (which were historically distributed by a codebook, different for each day). For each rotor we have $94$ possibilities, therefore for the whole setup there are $94^N$ possibilities. Then, each rotor can have two directions, hence $2^N$. The flow direction, I assume, is global, therefore we finally multiply all of this by $2$.

So, for the calculation, we have

$$ \log_2(1147^N \cdot 94^N \cdot 2^N \cdot 2)\\ = \log_2(1147^N \cdot 94^N \cdot 2^N) + \log_2(2)\\ = N \cdot \log_2(1147 \cdot 94 \cdot 2) + \log_2(2)\\ \approx N \cdot 17.718 + 1 $$

You will therefore have over 128-bit keyspace with 8 rotors and you will need 15 of them for 256-bit keyspace.

As previously noted by Adrian K Luis Casillas [edit], it doesn't mean this cryptosystem has this much "bits of security". This notion is much less strict and takes cryptanalysis into account, e.g. a cryptanalyst can find the attack which, after collecting sufficient material, will reduce the effective key space by either a couple of bits or even a large factor, halving it or worse.

Note that if you have any objections for this analysis I will happily discuss this topic further. It has been fun.

$\endgroup$
9
  • $\begingroup$ That gives me a much clearer picture. FYI, the performance I'm getting at the moment is such that using 100+ rotors is quite feasible. $\endgroup$
    – Adrian K
    Jul 27, 2017 at 8:12
  • $\begingroup$ The calculations you've done, where N is the number or rotors, am I correct in thinking the total you've arrived at is for that number of rotors exactly, and doesn't include accounting for permutations of lesser rotors? I mean for a brute force attack you'd need to consider those permutations as well? $\endgroup$
    – Adrian K
    Jul 27, 2017 at 8:23
  • $\begingroup$ I am not sure if I understand this design perfectly. Is it using more rotors than those selected by the operator? $\endgroup$ Jul 27, 2017 at 10:12
  • 1
    $\begingroup$ OK, now I see what you mean. Yes, indeed not knowing the number of rotors would make things harder for the attacker, replacing N as coefficient in the final formula with (N^2+N)/2. Yet, it would leave us with another problem: there will be weaker and stronger keys, depending on the chosen N. This property, having a significant portion of weak keys in the keyspace is what designers of cryptosystes try to avoid. Yes, the formula is correct, as are the results. If you supply the derived formula instead, you won't run into big number issues, and you will get 1755 bit keyspace for 100 rotors. $\endgroup$ Jul 27, 2017 at 22:21
  • 1
    $\begingroup$ FYI, project complete - you can get the app for free (but needs Windows 10). For more info see: morphological.wordpress.com/projects/enigma-x @Hubert Jasieniecki $\endgroup$
    – Adrian K
    Apr 9, 2018 at 23:50
2
$\begingroup$

The key size is just the length of a key when expressed in some code—some system for representing the key as a finite string of symbols drawn from some alphabet. If there are $n$ distinct keys and all of them are equally likely, then the length of a key in an optimal code with an alphabet of $b$ symbols is $\log_b(n)$. For binary codes we have $b = 2$, so you can just take the base two logarithm of the number of distinct secret settings in your system and reasonably call that your system's key size in bits.

Note that the key size isn't the same thing as the security level—your system may well be vulnerable to attacks quicker than trying all possible keys (as the real-life Enigma machines were).

$\endgroup$
1
  • $\begingroup$ I kinda get you. One way to express the key for my system (as described in the linked write-up is [rotor index, from the 1147 collection].[the starting index of the rotors rotation, out of 94].[rotation direction, out of 2] - repeated for as many rotors as you like. E.g a simple key would be 0.0.1/1.0.1/2.0.1 (for a 3 rotor key). $\endgroup$
    – Adrian K
    Jul 27, 2017 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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