Schneier on Security

Clive Robinson • May 3, 2018 7:15 PM

@ All,

The “gold standard” for a “hand cipher” is that it can still be used secretly and securely whilst under the full observation of a potential enemy. That is you can use it in say an airport lounge with CCTV and still be reasonably certain you are secure.

This kind of eliminates the likes of “code books”, standard One Time Pads and obvious cipher devices even using graph paper etc.

As @John MacDonald indicates above,

There is a big advantage in not looking odd – the hardest code to break is the one that is not noticed.

As I mentioned on a friday squid a week or so ago, carrying a couple of packs of cards, and a couple of dice is not suspicious. You can probably also get away with a Cribbage Board to use to do your “adds mod 26” etc for a stream cipher.

What you need to do is find some inoffensive way to both seed and run the Stream Generator / Psudo Random Generator. As I have mentioned before there are games of patience such as “Madman’s patience”[1] that with only a tiny variation in the way you play them will never end.

However they tend to be biased in their “raw output”. Supprisingly to many this is an advantage not a disadvantage when you are being watched.

As some hear will know if you take two independent bits from a biased random generator you can put them into an XOR gate and use that to select a given bit or no bit. The process actually “perfectly” de-biases the generator output you are going to use[2], whilst an observer just sees the biased stream output. The down side is simple as it is, it’s entirely possible that the de-biaser will never put a bit out, even though there may be usable entropy in the stream output. The von Nuemann de-bias process is,

1, Generate two bits of output.
2, If the bits are the same value go to step 1.
3, Output the first of the two bits.
4, Goto step 1.

It’s not difficult to see that step 2 is the XOR function. Further it is possible to see that the generator will have runs of “equal value bits” that change randomly. Thus the XOR test will put the de-bias back to step 1 without outputing a bit, although if you examine the sequence it definatly has entropy in it.

Further and importabtly it can be seen that on average you will only output one bit for every four generated. This means that the observer will on average see four bits, three of which serve no purpose in the stream cipher.

Whilst I’m not suggesting you use the Von Nuemann de-bias, there are other de-bias schemes you can look up that will work mod26 or mod36 sufficiently easily that you can do them in your head[3] with only a very little practice. After all you don’t want to use twenty or twenty four generator outputs just to cipher one character, though it might confuse the heck out of any observer.

Whilst I am quite fond of “card shuffling” algorothms as a way to make Stream Ciphers, most published designs “don’t look natural” when being used even after lots of practice, due to the use of jacks etc as “pointer/marker cards”. Thus the likes of Solitair will fail the “under observation” test.

It’s why I suggest “patience / solitair” games that will shuffle the deck, with bias, but importantly be natural to deal out thus look like a game of patience rather than a very very awkward thus highly “hinky” pointless shuffle…

What you do have to watch out for though is “repeating cycles” where the generator in effect gets stuck in a relatively short cycle. There are known ways to avoid this issue[4] but you need to be able to do them in your head, which can be somewhat harder than you might think.

[1] Madman’s patience is I understand called “Idiot’s Delight solitare” over in the US. If you have a look at,

https://en.m.wikipedia.org/wiki/List_of_patience_games

You will see that there are quite a few patience games listed at a little over three hundred (there are more than this there is a book published before ISBN’s were thought of that has something like five hundred games described, I’ve got a copy of it somewhere but can not put my hands on it at the moment).

[2] See the Von Neumann simple de-bias system, in :- Von Neumann, J., “Various techniques used in connection with random digits”, Applied Mathematics Serires, no. 12, 36-38 (1951).

Or have a look at, http://www.helsbreth.org/random/removing_bias.html

[3] Assuming you have a debiased binary stream, the number range you want may well not be a power of two. There are various ways to do this sort of thing, but the usuall recomendation (see Knuth) is to “drop any numbers outside of the range you want and get the next output from the generator”.

[4] One way around this is a variation of the Mitchell-Moore generator you will find in Knuth. It is at the base level a Linear Feed Back Shift Register (LFSR) on it’s least significant bit (LSB). However what you do is implement it as a circular buffer where you add two values and use the resulting output. Appart from the LSB the ADD function and XOR function are not very related, which is why they get used in ARX type ciphers.

Clive Robinson • May 4, 2018 4:16 AM

@ JasonR, Chris,

While an interesting exercise, it seems to me that a secret must be transmitted securely ahead of time, assuming in person.

A shared secret has to be established for any symetric encryption system to work. This is true for nearly all Internet traffic, the only question is how the shared secret is established.

It can and frequently still is being achieved by a face to face meeting either directly or through a trusted courier using Diplomatic Bags or some other semi or fully covert method. This is even done in commercial organisations that still use HF and similar long distance radio communications, where the One Time Pads used for emergancy key establishment etc are couriered from Head Office “Home Station” to “out stations”, vessels or mobile teams etc.

That said the Internet would not be where it is today without mathmatical developments in the 1970’s of Public Key and other forms of asymetric key ciphers or the key establishment protocols of Whitfield Diffie and Martin Hellman.

The reality is though these mathematical ciphers are both slow and many believe comming to the end of their working lives. The first is the reason why they tend to be only used for establishing a relatively short secret between two parties (ie an AES key etc). The second caused by advancments in Quantum Computing (QC). Which is why there is a bit of a scramble on to find new QC-proof algorithms that might be considered “efficient”[1].

The point is symmetric algorithms require a secure covert side channel atleast once to establish a shared secret. Having to go back to the way we used to do it before Netscape developed what would become SSL due to QC developments would almost over night kill e-Commerce.

As @Bruce noted a couple of decades ago cryptographers need to move on from finding new base crypto algorithms and get on with solving the Key Managment (KeyMan) issues that Key Distribution forms just a tiny part of.

Which brings me onto “OTP failings” all the failings of OTP systems fall squarely under failures of KeyMan be it poor Key Generation (KeyGen) of the pad through to poor Key Distruction after use.

Though most do not realise it KeyMan with systems that pre-date the mathmatical ciphers was an immense and easy to get wrong process, that usually failed horribly on trying to “scale up” beyond a handfull of communicating parties.

During the Cold War those running agents in the CCCP decided that for security and to ease KeyMan issues to use a hub/star “through home station” system for traffic flow. That is the agents did not communicate with each other but only through “home station” using One Time Pads. Unfortunately for the CCCP their KeyMan system was not upto the task and what should have been a secure system failed[2].

Which brings us to,

Further, the encrypted code must be transmitted somehow, so just how source/destination anonymous can it really be?

That is a “how long is a piece of string question”. In part because not both parties need to remain covert.

During WWII Admiral Karl Donitz who ran Germany’s U-Boats was faced with the communications and location security issue. He chose to use two different modes of operation and changed one of them several times during the war. He used a “Fleet Broadcast” system to send orders etc to the U-Boats, because although the location of the U-Boats was secret, the location of his headquarters transmitter was not. A mistake made in the early part of the war was to use a “Key Schedule” where all U-Boats used the same key for quite long periods of time. Initially it was felt that Radio Direction Finding (RDF or HF-DF also called Huff-Duff) would be insufficiently accurate to pin point a U-Boat provided messages were kept short. However the accuracy of RDF increases as the range decreases, with the “convoy system” the British had develiped in WWI there would be numerous radio operators on most of a convoy’s larger vessels maintaining a “listening watch” and would communicate Ship to Ship via Aldis Lamp to maintain radio silence of any traffic heard and it’s direction and strength. This gave “early warning” as the U-Boats MO at the time would be to spot a convoy and then fall back, radio the location back to get more U-Boats to in effect setup an ambush ahead of the convoy.

In most cases the Alies were reading the traffic due to weaknesses in crypto security, even though RDF was working sufficiently well. Eventually the German’s moved the communications system to a more secure footing, but this was not untill the very end of the war where it largely did not matter any more.

A study of maritime communications during major conflicts can tell you a lot about how to do “point to point” broadcast communications in more secure ways. However whilst the Internet does provide what appears to be point to point communications, it very rarely if ever is. That is most traffic gets routed through quite a few intermediate nodes. The nodes can be setup to deal with traffic in what is in effect an anonymous manner. The Onion Router and various Mix-Net protocols do this, however they are usually implemented in an insecure way thus are quite susceptible to “traffic analysis”. These problems can be fixed but there appears to be a lack of will to do so, which makes quite a few people suspicious about Tor.

Yes you can have difficult to impossible to trace traffic on the Internet if you wish but there is a price to pay. One of which is “latency”, the less you are prepared to tolerate the easier traffic analysis is…

[1] Many proposals for QC-Resistant/Proof crypto have failed under more advanced research which is on going. Others because the key size of thousands of bytes makes them inefficient or impractical, long before you find they arr computationaly slower “than a one legged dog”.

[2] Both the British GCHQ and US NSA SigInt agencies worked on the CCCP codes under the BRUSA –later UKUSA– “Five-Eyes” arrangement and it was known as Project VENONA. For what would at first appear a hopless task, it is attributed with some astonishing successes over it’s 37 year life,

https://en.m.wikipedia.org/wiki/Venona_project