Schneier on Security

Clive Robinson • July 9, 2012 6:54 AM

@ wonndering,

This appears to answer my question as to what ength a truly random AES symmetric encryption key has to be to ‘make it’ in the big city

Err no, it’s a best case baseline as it ignores some points where it can all go horribly wrong.

As noted AES has three basic key sizes 128/192/256 bits, if you actually want entropy to those values then you need to generate it to quite a bit in excess of that if you want it to be not just in any way human memorable but even easily typable from a “wallet cheat sheet” (such are the failings of humans).

So with a choice of 96 keys for each keypress you get in theory 6.6bits of entropy so the minimum for 128bits is, 128/6.6 = 19.3939keys as the minimum. But this is “theoretical” and not “actual”. In many cases theoretical is significantly insufficient due to the way you get from keyboard keys entered to AESkey bits and in some cases the anoyance of “line discipline” converting certain combinations of keys into a single key (think HTML %(ascii#) or \ conversion or MS-DOS IBM PC Key code conversion). Then there is the issue that the 96 key choices have issues in the probability of each bit being a one or zero in it’s normal binary representation, that is each bit has bias, generaly being worst in the higher bits. Then of course 96 does not map conveniently into 2^n representation as it’s 2^6+2^5 (64+32).

The usual way to do things (please note I’m not advocating this) is to have a “free text entry field” for a pass phrase, that you then hash in some way. So say take the ASCII string and run it through MD5 a number of times using cutting and splicing to try to get the best out of the entropy available.

So generating a “random password” can be seen as a series of transforms,

1, Get required number of bits of entropy.
2, Break into fixed size bit blocks.
3, Map block to one or more of the 96key choices.
4, Fixup any line discipline issues and format for humans.

Stages 3&4 waste entropy for a number of reasons so the required bits of entropy in stage 1 can be considerably larger than expected. Roughly 1.5-2 times larger, so for 128bits of AESkey entropy you are looking at 192-256 bits out of your entropy source. And depending on mapping, line discipline, and formating fix ups you could end up with a “free text” password likewise 1.5-2times bigger than the theoretical base line.

However there is another group of issues to consider which is how often you are going to change AESkeys and for how many systems and if you are going to use Master Keys, User Keys and Session Keys etc all tied up with two main issues,

1, Preventing “AESkey Re-use”.
2, Secure AESkey distribution.

Which is the “Devil’s Brew” of Key Managment systems. The first has various potential solutions that have been suggested. The second however is a real nightmare and depends on who your adversaries are (see Ross Andersons type 1 / 2 / 3 definitions). For instance with a type 3 adversary getting off an aircraft with KeyMat in printed or recognisable stored form (thumb drive etc) has a very high probability of being copied on your way to clearing air side (even if you have hidden it in your underware etc). Likewise with Post, Telegram, or any kind of Internet comms. So you have to consider how to make the capture/copy of KeyMat in transit usless to an adversary.

All of which has a significant effect on how much entropy you are going to need from your generator and just how good it needs to be. In most cases a single generator type is insufficient to fulfil even quite modest KeyMat requirments.

So hybrid systems are currently in vogue where you use the likes of a True Random Number Generator (TRNG) to make Master and User Keys and Seeds for determanistic but Cryptographic Secure Pesudo Random Number Generators (CSPRNG) like AES in CTR mode to limit key re-use.

Having had to go through the design process of TRNG’s and getting them “certified” as acceptable for requirement, I’m not that impressed with the majority of “supposed” TRNG’s running on PC’s. If you want to know why Bruce and Niels Ferguson have tried to design a couple of acceptable systems (Yarrow and Fortuna) and their published notes on their design and mitigation of issues should give you an idea of what’s involved. There are even “provably secure” CSPRNG’s such as Blum Blum Shub.

However they all have disadvantages in that their output rate may be way to low for many systems. So there is the idea of ‘spreading the goodness” of an entropy sorce across a determanistic process. One such is to use ARC4 as a rapidly evolving pool of deterministic numbers into which you stir the entropy from your source. there are a number of ways to do it one being to add the entropy into swap function (ie expand. Sary[Iptr + Jptr] to Sary[Iptr + Jptr + ent]) which is the same as the initial ARC4 key loading/update process (except the entropy replaces the stored key).

Back in the 1990’s I used a BBS generator to generate the “entropy” into an ARC4 type system where the Sary was actually 1024 values in size not 256 but the output was moded down from 10bits to 8 after it was post “whitened” by the output of a digital low pass filter applied to the output of a large Mitchell Moore generator (see Knuth for details on MMG). The result looked like the output of a CS-TRNG [1] under the tests then in use.

Which possibly says more about the state of the then tests than the quality of the generator.

[1] A CS-TRNG is a TRNG with it’s output modified to make it of use in crypto activities. This is because TRNG’s have some decidedly unhelpfull output possabilities in that an unbounded string of 1’s, 0’s or repeating pattern is to be expected as part of “normal operation” [2] all be it at a proportianatly low probability. That is you don’t need an OTP with excessive runs of 0’s as the plain text comes through. The usuall method is to use an “unbiasing” technique such as set some kind of limit and then drop further repeating output and flag an error for each drop [3].

[2] The “normal operation” of excessive run lengths might also be an indicator that there are issues with the generator such that it’s “noise source” is becoming faulty [4] or under external influence by some form of “fault injection” either directly or from a distance deliberatly or accidently (ie it’s not sufficiently screened to deal with the 1KW HF transmitter in the room next door who’s TX antenna is on the roof just above, which can be considered normal on “ship board” usage, or the fact that someone has put it directly ontop of an old CRT monitor etc etc).

[3] It’s important to flag errors as close to the noise source as possible and certainly prio to the addition of “magic pixie dust” hashing etc. The errors should be looked at both in real time and statisticaly over time as the analysis of the “drop” error flag frequency etc may reveal the type of issue if it’s not low probability “normal operation”.

[4] Noise sources used in TRNGs are notoriously fickle and very very susceptible to environmental conditions such as EM fields E and H components and even mechanical vibration or acoustic sources effecting components being picked up by components such as powersupply filtering and EMI components such as inductors.