IIT Alma Mater

A few years ago, the school where I work decided to change its Alma Mater because nobody could remember the tune, and much less the words. There was a contests and, what do you know, I won (against very little competition, truth be said). Read on to see the words and hear the music of “IIT, You Mean to Me” (or, “IIT, you’re mean to me,” as most people sing it). Read More

Calculator-based cryptography

You think you need a computer to have a high-security code? Think again. I am about to tell you how to encrypt a message with as much security as you want, using just a common calculator. The name of this code is “root”, because the calculator’s square root key is what makes it secure.

Let’s say you have an important message you need to transmit, but your enemies have tapped your phone, fax, and email, and you suspect they have infected your computer with a worm that will relay to them everything inside. Let’s say your message is:

MEET ME AT THE TRAIN STATION

The first thing you have to do is convert each character into a two-digit number from 00 to 99, following a code you have agreed with your friends. This gives you room for all letters in the alphabet, plus numbers, plus a whole lot of special characters. Let’s say the code gives 00 for a space (though often it is better to eliminate spaces and punctuation altogether), and then the letters are numbered in alphabetical order: A = 01, B = 02, C = 03, and so on. Then the message becomes:

13050520 00 1305 00 0120 00 200805 00 2018010914 00 19200120091514

Of course, cracking this would be child’s play for just about anybody, so we must conceal it under something really difficult to guess. Here’s where the calculator comes in handy. But before you begin, you need to have two more things. The first is a secret passnumber, which you have agreed with your friends. You have memorized this passnumber and never ever written it down. If you find it hard to memorize a long number, then use a password made of text, but you must convert it to numbers, as described above, before you can use it.

Let’s say your passnumber is:

123456789012345678901234567890

Its length is a function on how many digits your calculator can handle. It should be a little shorter than a multiple of the calculator’s precision. Here I assume you have a 12-digit calculator (many desktop calculators can do that; the more digits, the better). Your friends should have an identical calculator, or the code will break down.

The second thing you must have is a serial number for your message, which you must produce right now. The only trick is that you should never exchange two messages with the same serial number (in either direction), or the code will be exposed. The length of the serial number is equal to a multiple of the calculator’s precision, less the passnumber length. Since we use 12-digit calculators and a 30-digit passnumber, that leaves 12×3 – 30 = 6 digits for the serial number, with enough room for a million different messages.

Let’s say you pick this serial number:

555555

Now append the serial number to the passnumber and break the whole thing into groups of 12 digits, like this:

123456789012

345678901234

567890555555

Now comes the tricky part. You must convert these into three kinds of mathematical entities: multipliers, adders, and a seed. Since you have only three numbers, you’ll have one of each. The multipliers have half of its figures as integers and half as decimals (because of the 12-digit precision, since 12/2 = 6 integer figures; if we had a 14-digit calculator, then you would take 14/2 = 7 integer figures). The adders have two fewer integer figures, in our case, four. The seed is all decimals, and it contains the serial number as its tail. Thus, you have:

Multiplier = 123456.789012

Adder = 3456.78901234

Seed = .567890555555

Now you enter these numbers into the calculator and perform the following calculation:

Result = fract(sqrt(Seed * Multiplier + Adder))

In other words, you take the Seed, multiply it by the Multiplier, and add the Adder. Then you take the square root of that result and subtract the integer part so that only decimals remain. With the numbers of our example, this is:

Input Result
.5678905555 x 123456.789012 = 70109.944492
+ 3456.78901234 = 73566.7335043
do square root = 271.231881430
– integer part (that is, 271) = 0.231881430
new Seed

The last number obtained becomes the new Seed, and the process can be repeated. If there are more adders and multipliers, the next time a different set of Multiplier and Adder is used. When all the adders and multipliers have been used once, you look at the digits of the final result, which add to the encrypting “keystream”. In the example, they are:

231881430 (all zeros count, except the one on the left of the decimal point)

Then you write those numbers underneath the message (turned into numbers), and add the two together neglecting carryovers (so you can do it from left to right). If there are not enough digits in the keystream, you generate more with the calculator, starting with the last result as Seed but using the same adders and multipliers, until there are enough. Your message has 56 digits but the calculator has given you only 9, so you need to do it six more times. It is convenient to store adders and multipliers in memories (which you will erase when you’re done, right?) to save work. In this way, you get:

message: 13050520001305000120002008050020180109140019200120091514
+ encrypting keystream from calculator: 23188143012042259736534369536548841140602240348004490344….
= combination: 36138663013147259856534369586568921249742259748124481858

where the last sequence of numbers is obtained by adding the other two digit by digit, neglecting any carryovers (that is, 8+7 = 5, not 15)

Now you only have to send your friends this last sequence of numbers, plus the serial number (as a list of phone numbers, or stock prices, or whatnot), confident that nobody who doesn’t have the password will be able to decipher it. So, this is what you would send more or less in the open, assuming you have agreed to place the serial number at the very beginning:

55555536138663013147259856534369586568921249742259748124481858

Your friends, after retrieving the serial number from the message itself and the passnumber from their own brain, will be able to produce the exact same encrypting keystream from their calculator, and they will subtract it (again, neglecting any carryovers, so that 5 – 7 = 8, and so on) from the transmitted message, in this way:

transmitted message: 36138663013147259856534369586568921249742259748124481858
– encrypting keystream from calculator: 23188143012042259736534369536548841140602240348004490344….
= retrieved message: 13050520001305000120002008050020180109140019200120091514

And now they can easily convert every two-digit group back into characters:

MEET_ME_AT_THE_TRAIN_STATION

That’s it! Now anyone can enjoy high-strength encryption without the help of a computer.


Now, you’re probably wondering, how strong is this cipher, really? The short answer to that question is: that depends on the length of the passnumber and on how many digits your calculator can handle. The more digits in either, the better.

A long passnumber ensures that a lot of possibilities must be tried by anyone trying to crack the message by brute force. If the passnumber is thirty digits long, that’s 10^30 different numbers to try. This is comparable to using a 99-bit binary key, which is just about twice as long as the 56-bit key of DES encryption, used by the US Government until recently. A team of determined hackers cracked DES by brute force in just about 23 hours in the year 2000. Assuming that Moore’s Law holds (that computer power increases by a factor of ten every five years, for a constant inflation-adjusted cost), the same team wouldn’t be able to crack your 30-digit encription by brute force in under a day until sometime in 2065 AD. Even giving the NSA a ten-year advantage, that’s still pretty good for most of us.

If this isn’t enough for you, you can always use a longer passnumber, since every digit added increases the cracking difficulty by a factor of ten. Now, this is best done by chunks as big as can fit in the calculator. So, if you use a 12-digit calculator, the next thing to do is to use two multipliers instead of just one, and then the next to use two multipliers and two adders. The digits added to the keystream are those obtained after all the adders and multipliers have been involved. And so on, and so forth.

Additional security can be gained by using a special “message key” instead of passnumber+serial to generate adders, multipliers, and seed (just in case you make a mistake and use the same serial number twice, more on that later). In this case the process goes the same way, except that the first series of digits coming out of the calculator are used to make a new set of adders, multipliers, and seed, and then the keystream is produced starting from those. This added step forces your generating numbers to be completely different from message to message (not just the few last digits of the seed), and thus your master passnumber is never exposed in any way. I recommend using this precaution, which does not add that much extra work anyway (because you’re going to burn the paper containing your calculations, right?).

It is important to make sure that the serial number is never reused (by either side of the transmission), because then the same encrypting keystream would be used for two different messages. An enemy could then eliminate it by subtracting one message from the other, leaving a superposition of two unencrypted messages that would be quite easy to crack by letter frequency methods. And on top of that the keystream would be revealed, from which it might be conceivably possible to extract the numbers used to generate it. This is a bad feature of all “stream ciphers,” like this one, but they also have good features that other ciphers don’t have. For instance, in most ciphers any mistake garbles the end result completely, but in stream ciphers only the characters encrypted after the mistake end up garbled, which makes it a lot easier to spot the error and correct it. Handy when it’s just you punching keys.

And how about the calculator? If it uses too few digits (many pocket calculators display only eight), then the pseudo-random properties of the keystream suffer, and the message is exposed to statistical analysis. The sequence will also start repeating after a while, which is bad. In my experience, eight digits is no good, ten is barely acceptable, and twelve and above work fine. The more digits, the better. I have a Palm-based calculator that can operate with thirty-eight digits at a time, so it gives me better security than the current AES governement standard (256-bit) without even using an adder.

You have to thank irrational numbers for this cipher. The digits of irrational numbers obtained from a square root, like the square root of two (1.41439799432119332181380109536190378…) never repeat, and appear random to anyone who doesn’t know where they came from. It is this apparent randomness that conceals your message in noise, rendering it impossible to read.

 

Perpetual motion from light

Perpetual Motion Machines are those that would produce free, endless power, thus ending all of humanity’s energy problems (and maybe some political ones at the same time). I am not going to embarrass myself showing pictures of my early perpetual motion machines on this page, since you can find some very similar ones (guess which ones they are) going to this excellent website. What this article is about is a kind of perpetual motion machine that so far I haven”t been able to prove how it doesn’t work. Maybe you will…

What is Perpetual Motion?

Perpetual motion refers to a device that produces free power forever. This does not apply to things like the motion of the earth or the moon, because those would eventually stop if we extracted power from them (in fact, the moon always shows the same face toward earth precisely because, when it was young and soft, the energy of its rotation was “extracted” into tides that eventually died down). The motion of the heavenly bodies is actually inertia, not “perpetual motion.”

Many people have tried to invent (or, more likely, pretend to have invented) devices that produce free energy. Such devices, or “perpetual motion machines,” can be classified into two broad categories:

  1. First Kind: devices that create power out of nothing.
  2. Second Kind: devices that extract power out of the environment.

The first and second laws of Thermodynamics derive from the impossibility (so far) to build these devices. The first law tells us that energy must be conserved, and thus it is impossible to make a device that will generate power without consuming some other kind of energy. The second law states that, once energy has gone into the environment, usually converted in to heat, we cannot get it back as useful power: energy is indeed conserved, but it can be degraded.

Throughout history, attempts at perpetual motion of the first kind have usually centered around imbalanced levers, where a clever mechanism shortens one of the sides of a see-saw, for instance, as it rolls around to the opposite position from where it started, or on magnets. I can claim the dubious honor of having invented (or rather, re-invented) machines of both types, before I knew any better (or even after ;-).

Putative perpetual motion of the 2nd kind is a bit more sophisticated and hard to detect. The giveaway usually is the lack of a heat sink in machines that absorb heat from the environment. The same website has a number of pretty interesting machines of this type, so I will only add here those you cannot find there. I happen to know personally the inventor of a few of them, which have obtained (fairly recent) patents from the US Patent Office, despite their long-standing policy. This is either a witness to the lack of training of the examiners or to the insistence of my friend the inventor. Maybe to both. Here are links to those patents:

4,479,354     4,663,939     5,107,682    

But I want to tell you about different types of perpetual motion. Here I will tell you about how light can be used to seemingly create perpetual motion of the 2nd kind. A new type of perpetual motion, which I would call “of the 3rd kind,” and which does not seem to be violating any physical law so far in force, is explained in this page.


Perpetual motion from light

Electromagnetic radiation is a strange beast as far as the Second Law is concerned, because it behaves either as heat or as work, depending on the circumstances. It is heat for a hamburger warming up in a microwave oven, but it would be work, capable of moving electrons in an ordered, spark-generating way, for a fork inadvertently left inside. Light is electromagnetic radiation, and because of this it sometimes behaves as heat, as in a black body glowing due to its temperature, and sometimes gets diffracted and aligned like the millimeter waves that link your cell phone to the world.

An interesting result of diffraction is holography. A hologram is a two-dimensional image, usually on film or a similar, fine-grained substrate, that actually contains a three-dimensional image. It is generated by shining a laser on the 3D object to be recorded while at the same time shining an identical laser on the film. The film will be exposed with a series of very fine lines, which look kind of like what you get when you put a semitransparent fabric on top of another, such that the image will be reconstructed by shining yet another identical laser (or a non-laser light of the same color) on it. Holograms have a lot of interesting properties in addition to looking really cool, and one of them is that you can record multiple holograms on the same film and they won’t interfere with one another so long as the laser shining directly on the film during recording (called the reference beam) changes in color or position from shot to shot.

This property is used in US patents 5,877,874 and 6,274,860 by Rosenberg (assigned to Terrasun, Inc.), to create a film that directs sunlight into a narrow beam no matter what direction it comes from. Thus, a solar panel having this film in front of it would not need to turn to track the sun, which is quite handy. This is the intended application of the film, which allegedly has been tested in a number of prototypes. The patent descriptions can be found here and here. Below is a picture from the first patent, which illustrates the concept:

All right, then. Imagine we have a piece of this film, made so that all the light (and infrared radiation) falling on one side of it will be transmitted through to the other side, where it will leave in the direction perpendicular to the surface no matter what direction it came from on the other side. This film would be the heart of the device in the picture below:

In addition to the film, the device includes a large flat black body 1, a small black body 2, and a parabolic mirror, which has black body 2 centered on its focal point. The side surface between the large black body and the film is also polished to mirror finish. All surfaces are thermally insulated on the outside.

For those whose heat transfer courses are a bit rusty, a black body is a type of surface (actually, an ideal surface, but we can get pretty close in reality) that absorbs all the radiation that falls onto it. That’s why it’s called “black,” because it absorbs all light that falls on it and thus our eyes register its location as black, but it is also “black” for thermal radiation as well, which is mostly in the infrared range and our eyes cannot see it. When hot, a black body will emit radiation at a rate given by this formula:

where A is the surface area, s is the Stefan-Boltzmann constant (5.67×10-8 Watt/m2K4), and T is the black body absolute temperature, in Kelvins (temperature in centigrade degrees + 273.15).

Now we do the following: heat up black body 1 to a (high) temperature T1, and wait until thermal equilibrium with black body 2 is established. Thermal equilibrium means that no heat flows from 1 to 2, or from 2 to 1. The 2nd law of Thermodynamics (through a corollary mistakenly called by many “the zeroth law”) commands that this shall only occur when the temperatures of 1 and 2 are the same. But let’s see if that is the case here.

Observe that, given the geometry and the presence of the holographic film, all radiation issuing from 1 will hit the film, where it will be made parallel and transmitted to the other side. Now, a parabolic mirror has the interesting property that all beams parallel to its axis are reflected toward its focus. This means that all the radiation will end up on black body 2, where it will be absorbed. No radiation will bounce back to the surface of 1 (this is important). The heat rate going from 1 to 2, therefore, is given by:

 

But black body 2 also emits radiation. Some of it will bounce on the mirror and then back to the surface of 2, but most of it will miss it after the reflection and will travel toward the film after that. A lot of the radiation will travel toward the film directly. This means that eventually most of it will end up on the film, where it will either be steered toward the perpendicular direction or will be somehow diffused as it travels to the other side. In either case all of that radiation will end up on surface 1, as given by:

 

where the factor f, representing the fraction of the heat radiated by black body 2 that ends up falling on black body 1, is less than, but close to 1. When thermal equilibrium is reached, both heat flows balance one another, so that:

 

and then, it follows that:

 

Since A2 is smaller than A1 and f is less than 1, the temperature of black body 2 is greater than the temperature of black body 1 when equilibrium is reached. This makes it a perpetual motion machine of the 2nd kind, because now we can run a heat cycle using black body 2 as a heat source and black body 1 as a heat sink, and thus generate some power.

Now let’s discuss some things that might possibly go wrong, and why they still wouldn’t keep the machine from breaking the law.

1. It could be said that there is no such thing as a perfect black body, and neither is there a perfect mirror, or a perfect insulator, or a perfectly transparent film. True, but the 2nd law is supposed to apply even if they existed, for it is based on infinitely slow, ideal processes, which are the limit of real processes. It’s just not fair to a candidate perpetual motion machine to force it to deal with non-ideal materials. You can stop anything, including machines that don’t violate any laws, by heaping friction, losses, and leaks onto them.

2. There is a similar putative perpetual motion machine based on elliptical mirrors with black bodies in their foci. You can find it here, and here, (courtesy of Prof. L.H. Palmer, from Simon Fraser University). This is what it looks like: 

The mirror geometry supposedly conspires to put more energy on black body 2 than on the other because some of the light coming out of black body 2 will be reflected back onto itself but not so for black body 1, but this is only in appearance. In reality, since the bodies are not mathematical points some of the energy coming out of one will fail to strike the other (this happens for both bodies), so that eventually the device will be filled with a uniform radiation intensity, and therefore both bodies will end up at the same temperature. The problem here is that the same argument does not work for the device we’re dealing with, since all the radiation coming out of black body 1 is guaranteed to fall on 2, even if it is not a mathematical point (and even better if it’s not), and any radiation that, coming out of black body 2, does not strike 1 but falls back onto 2, only makes the temperature difference even greater (through the effect of < 1).

3. It could also be that the holographic film cannot steer the incoming radiation into exactly parallel beams, but rather into beams deviating from the perpendicular by up to an angle q, so that, after reflection on the parabolic mirror, they will miss black body 2, leading to a uniform radiation field as in the device mentioned in the paragraph above. If q is sufficiently small, however, the rays reflected on the parabolic mirror will concentrate within a sphere of radius e around the focal point, where e is a continuous function of q with e(0) = 0. If follows that one only has to choose a spherical black body 2 with a radius larger than e, for all the radiation from black body 1 to fall onto it, which brings us back to the original situation. For a sufficiently small qT2 will still be greater than T1.

 4. Another argument is that, since the film patents only show films working by reflection, then the machine above will not work because it works by transmission of the light through the film. This is only an apparent problem. First, every reflection hologram has a conjugate transmission hologram, the difference being whether the reference beam used in recording the hologram is placed on the same side of the film as the object to be holographed (for transmission holograms), or on the other side (for reflection holograms). It follows that, even if the film patents do not specifically speak about transmission holograms (and they should), it should be possible to make them by putting the reference beam on the same side as the object beam during recording. In addition, it is possible indeed to make a similar machine as the one above using a hologram that reflects light into a single direction, no matter what direction it originally comes from, as in the next figure:

As in the transmission case, all the light issuing from the large black body 1 will fall onto the small black body 2, and the difference in surface area will ensure that T2 > T1. But this case is even more extreme than the transmission case because, if the film reflects into a single direction all the light that strikes it, then it does it both for the radiation going from 1 to 2 and for the radiation initially going from 2 to 1, which will end up falling back onto black body 2. This means that thermal equilibrium will never be reached, since no energy flows from 2 to 1, and temperature T2 can reach arbitrarily high values.

A simpler version of the above device would have no parabolic concentrator, like this, using films that reflect light at a 45 degree angle:

Because of the geometry, light from the right side never reaches the left side, so the black body on the right will keep receiving energy by radiation while losing none. This setup acts as a Maxwell demon for photons, rather than gas molecules.

5. One could say that, in practice, there is no such thing as a holographic film that steers all incident light into a single direction. The actual prototypes made by Terrasun (the inventors of the patents mentioned above), which I have seen in action, collect light from just a couple directions and send it in a broad beam in a different direction. It is doubtful whether a perfect or near-perfect light-steering film can be made in practice, since this would involve recording many holograms into a single film, and the superimposed holograms, although theoretically able to coexist, would end up interfering with one another so they could not work. So the next question is: how well do the light-steering holograms have to work in practice so they can still be the basis of a perpetual motion machine? The last machine above violates the 2nd law by impeding backward transmission of light, without any concentration, while the first does it by concentration, without needing one-way transmission at all. If both effects are combined, as in the machine in the middle, it may be possible to still achieve a violation with imperfect holographic films.

For instance, a film that does not steer light at all, but simply prevents it from being reflected into a certain region can still form the basis of a one-way light valve, as in the picture below:

Here the film would not reflect light into a certain angle off the surface. By shaping the film into a logarithmic spiral, it is possible to ensure that none of the light that enters the device from the left (or from the right), would come out of the left port, even if the light would be otherwise dispersed. If the “blind angle” for no reflection does not come all the way to the surface, the device would be more complicated, but I don’t believe it would be impossible to come up with an example.

Likewise, the concentration effect does not need to be perfect in order to work. Even the concentration due to a change of index of refraction can do the trick if the change is strong enough, as in this device:

Here there is no holographic film at all, but partial concentration is achieved by changing the index of refraction of the transmission medium, which we assume to be non-participating in the radiation. After crossing the interface, the radiation coming from black body 1 will be partially aligned along the axis of the parabolic mirror within the total reflection angle of the interface, given by:

where n1 and n2 are the indices of refraction of the transparent media in contact with black bodies 1 and 2, respectively. This angle is measured from the perpendicular direction so that, the greater the ratio of the refraction indices, the more aligned toward the perpendicular (which also happens to be the axis of the parabolic mirror) will the light be. As we saw before, the light does not need to be fully aligned with the axis of the parabolic mirror in order to strike a surface smaller than the emission surface, leading to a temperature imbalance.

On top of all that, holograms, interfaces, and other components in the device do not need to work equally well with all the wavelengths in the spectrum, as indeed they won’t. To see this it is enough to imagine that the blackbody surfaces are coated with a filter film or paint that only allows a certain wavelength to pass through. This narrow-pass film is certainly ideal, but there are existing films that approximate this behavior quite well. In that case, all the radiation involved in the exchange will be of a single wavelength, but everything we have discussed above would still hold and there would still be a heat transfer imbalance and a temperature difference would be created.

Conclusion:

I would probably get kicked out of my job as a professor and defender of the 2nd Law of Thermodynamics if I said that these machines could work, so I won’t say that. But I will say this: they’re stumping me so far and sometimes manage to take away my sleep (well, part of it, really :-), so please let me know if you come up with a more convincing argument why they cannot work (other than saying that they seem to violate the 2nd Law of Thermodynamics).

If, on the other hand, you decide to build one and succeed (they seem pretty simple, but I’m not that handy, and forget about writing a proposal to get funding for that), I’d like to hear from you. My email is elsewhere on this website. You will be assured strict confidentiality, because I know what you’re likely to get if your machine actually works and Uncle Sam finds out about it (hint: definitely not a patent, how about a nice vacation at an exclusive resort in southern Cuba?). Should they find me, the only line that’ll cross my lips will be:

Eppure si muove!

Possible perpetual motion

What do you know? It seems there is a new kind of Perpetual Motion Machine, which would give free energy for ever, and Nature hasn’t managed to pass a law against it (just yet, at any rate). Read on if you’re strong-hearted (warning: contents under heavy math)…

Perpetual Motion Machines of the 3rd Kind

This article is highly unusual because it deals with a perpetual motion machine that the laws of Thermodynamics forgot to forbid. Perpetual motion machines, in their most common definition, are those that produce a high-grade kind of energy, such as electricity or mechanical work, for free. Naturally this cannot be or the world would go topsy-turvy: fortunes would be reduced to poverty, governments would collapse, and the earth would start warming up for good. But thankfully, Thermodynamics has laws to prevent such mayhem.

The First Law forbids anything from yielding more energy than is put in, effectively nullifying machines made out of magnets, unbalanced levers, and self-regenerating motors. The Second Law, on top of that, sets a strict limit on the efficiency of the heat to work conversion, so those who thought to solve all the world’s problems by extracting plentiful power from the environment—where it eventually returns only to be recycled back to use—were forced to put their considerable creativity to better use. A perpetual motion machine is fool’s gold, our textbooks say, meant for the doom of those who did not bother to stay awake during Thermo class. Of course, the flaws of such machines are hard to see sometimes. This one, for instance, which is based on light.

Another perpetual machine (called by some of the “third kind” to distinguish it from those of first and second kind, loosely described above), has been proposed. The trick here is to get a mass (let’s say it’s an ice-cream bar) down to absolute zero. Then one could go to the nearest hardware store, buy a perfect Carnot cycle, and stick it on top of the absolute-zero ice-cream bar as shown in the figure below

The Second Law gives, for the efficiency of such a machine, this expression, where the temperature must be expressed in Kelvins of any other absolute scale:

Where TH and TL are the high and low temperatures of the cycle, respectively. If the low temperature in the cycle is absolute zero, then the efficiency of the set is exactly one, meaning that all the heat extracted to the environment will be converted into usable power. An additional benefit is that the heat rejected to the ice-cream bar will be exactly zero, so our precious property will never see its temperature raised above absolute zero. We can keep our machine running forever (remember, it’s a perfect Carnot cycle), creating useful power out of the environment. This, of course, is forbidden by the Second Law, so this machine is actually a special type of perpetual motion machine of the second kind, and giving it its separate kind is not really warranted.

Is there, then, such a thing as a true perpetual motion machine of the third kind?

Enter exergy. This very useful concept “discounts” energy to give its potential to produce useful work. For instance, the exergy of heat of value Q is less than Q, because not all of it can be converted into work, according to the Second Law, but rather:

where T0 is the temperature of the environment, which is usually the heat sink in common thermodynamic systems. Everything that contains energy contains also exergy, including things that contain no energy at all. For instance, an evacuated tank contains no material, and therefore no energy, but it can be used to generate power by causing the environment to push a piston or putting a paddle wheel in front of the onrushing air, should the tank be punctured. The important thing is not whether the power comes from the system or not, but rather that the system is the opportunity by which the system itself or the environment will be able to produce power.

The exergy of substances can be calculated in many ways, and it is usually related to its thermodynamic state and that of the environment, as given by its temperature, T0, pressure, p0, and other properties. The particular case of interest for our perpetual motion machine of the third kind is the exergy of a substance whose constituent molecules are able to evaporate into the environment. If that substance, say, behaves like an ideal gas (and every substance will, once its vapor pressure becomes sufficiently small), its exergy is given by the following expression (assuming its specific heat Cp is constant, for simplicity):

  

Where y and y0 are its mole fractions within the system and in the environment, respectively, and p and p0 are the pressures. The upshot of this is that the above formula, which is derived in strict compliance with thefirst and second laws of Thermodynamics, would give an infinite exergy whenever y0 is zero, that is, whenever a substance is completely absent from the environment. Creating a substance that is completely absent in the environment is not such a far-fetched concept, though. Pharmaceutical companies are doing it all the time when they synthesize new medicines. Physicists do it routinely, at a subatomic level, when they collide particles traveling at a high speed to create new particles. It takes more or less energy to form a new substance, but it is always a finite amount. The amount of work required is, at a minimum, equal to its “chemical exergy,” which is obtained when the compound is allowed to react producing work (say, in a fuel cell), or maybe absorbing work, down to compounds that are present in the environment, and those are then allowed to diffuse into this environment, contributing more work through terms of the same form as equation (3), but which are now finite because none of the y0 concentrations in the environment is zero. Of course, equation (3) is not supposed to be applied when a substance is completely absent from the environment, but rather one must first calculate how much exergy is required to generate the substance by chemical reaction, starting from substances that are present, and then add the exergy that those substances would have before they expand into the environment, as explained above. But then the paradox remains that a substance that required no infinite exergy to synthesize, would appear to have an infinite capacity to do work if it is simply allowed to expand into the environment.

For an example of how a true perpetual motion machine of the third kind would work, look at the figure below:

The “synthesizer” is a black box system where a certain new substance (let’s call it “novium”) is being synthesized, starting from substances present in the environment. This process, as we saw above and know from experience, takes a finite amount of energy, consisting of work and heat. The novium formed in the synthesizer now travels to an expansion chamber maintained at the same temperature as the environment, where it is vaporized and meets a membrane that is permeable to all the substances present in the environment, but not to novium. The membrane, therefore, will be subject to the vapor pressure of novium on one side, and no force on the other. If it is allowed to move, the membrane will produce a work as the novium gas expands at constant temperature, absorbing thermal energy from the environment. The process can move at a vanishingly small rate, approaching equilibrium at all times. The process is also reversible, since it is always possible to push the membrane against the novium vapor pressure until it is concentrated into a small volume. Under these conditions, and having removed friction and other irreversibilities, the expansion chamber will produce a work per unit mass equal to its exergy, given in the equation above. Since y0 of novium (in the environment) is zero, then the work produced, given an infinite stroke for the membrane displacement, will also be infinite. Another way to look at it is that the novium undergoes a constant temperature process. Since it is an ideal gas at low concentrations, the work produced will be given by:

 

leading to a logarithmic relationship between work and volume. Eventually, for a sufficiently large volume (it does not have to be infinite, in fact), the expansion chamber will have produced enough work to generate the required novium sample, and then some. It should be noted that equations (3) and (4), far from breaking down as the expansion progresses, would be less and less of an idealization, for all substances approach ideal gas behavior as their vapor pressure tends to zero.

The energy, of course, comes from the environment, mainly through heat interactions in the synthesizer and the expansion chamber. But the environment is at a constant temperature, so it should not be possible to produce any work by extracting heat from it, according to the Second Law. And yet, an analysis of the equations above says that this result comes directly from that law, since the logarithmic term that gives the infinite result can also be derived from:

where

  

is the entropy difference of an ideal gas (with constant specific heats) between a given state and the environmental state. Here the pressure used is the partial pressure of the gas, in case there are other gases mixed with it, which is the usual situation.

What has happened here? How did the Second Law manage to produce a result that seems to contradict the Law itself?

It should be noted that the fact that nobody has made, nor likely ever be able to make, such machine is no argument against the paradox. Likewise, nobody has been able to build something as simple as a Carnot cycle, because there are always irreversibilities such as friction and heat transfer across finite temperature gaps, and yet the science of Thermodynamics is based on it. No, the relevant fact here is that the machine proposed above, in its ideal form, seems a self-contradiction of the Second Law, which this law’s propriety cannot tolerate even in its most ideal form.

The reason why the machine is not a perpetual motion machine violating either the first or the second laws is because it does not really work in cycles. Indeed, after the first novium sample has expanded, producing as much work as we cared to collect, it is necessary to bring it back to its initial state. A valve opens on its far wall, and the membrane is allowed to move back under no pressure differential, venting the novium into the environment. But that means that, next time we try to expand a sample of novium gas, it will no longer be totally absent from the environment, and thus no infinite work will be possible.

Yes, but the same could be said about the Carnot cycle, which absorbs heat from a constant temperature thermal source without lowering its temperature, and rejects heat to a thermal sink without raising its temperature, either. The mental construct used is that those two “thermal reservoirs” are infinite for these purposes, and so a bit more or less heat does not change their temperature. It would not be fair not to give a similar capacity to absorb novium to the environment surrounding the machine, so that the concentration of novium in the environment will not be altered because a few (or a million) strokefuls are dumped in.

In addition, nothing prevents the machine operator from changing the composition of novium for the next stroke (along with that of the membrane). This is something that takes a finite amount of work, so that the next cycle works very much the same as the first, as far as the machine is concerned. There is no fear to run out of different substances to make, so the machine would keep working indefinitely. This is, however, strictly not the same process if the composition of novium has changed. We will revisit this aspect later on.

But perhaps such machine is intrinsically impossible, because no membrane will ever be able to distinguish novium from the other gases in contact with it, and thus it will stop performing as it should. The job we are asking the membrane to perform is indeed quite delicate, and not much different of the job performed by our good old friend, Maxwell’s demon.

Maxwell’s demon, pictured below, is supposed to stand guard by a little trapdoor, and allow only fast molecules to go from left to right, and slow molecules to go from right to left, with the result that a temperature difference is soon created, against the Second Law. But Maxwell’s demon cannot perform its job unless he analyzes the speed of the approaching molecules, and he creates more entropy doing so than he destroys by classifying the molecules into fast and slow. The question is, does a membrane suffer from a similar limitation? How does a membrane know novium from any other substance?

The answer is not simple, for semi-permeable membranes operate in many different ways. The membrane that is around every one of our bodies’ cells, for instance, has receptors of many kinds on its surface, and certain molecules can latch onto it by means of hydrogen bonds, provided their geometry matches that of the receptors. Scientists have been able to do a similar thing with DNA fragments on a silicon chip, using restriction enzymes that would only bind to specific sequences. If novium is DNA-based, then a substrate coated with a restriction enzyme for its particular sequence would be able to stop it as it tries to get past, while it would not stop any other molecule. The novium bound to the enzyme would eventually reach an equilibrium (controlled by the Second Law) with the free novium, so that as many molecules are released back into the expansion chamber as are captured on its surface. The result would be a barrier for novium, and the perpetual motion machine of the third kind would be able to run.

But it gets worse: making a membrane that would stop novium but would not stop anything else could be as simple as making the novium molecule larger than any other molecule present in the environment. A common wall with holes big enough for those, but not for novium, would do the trick. This is the laziest kind of Maxwell demon. A Maxwell demon who does not need to use any energy to classify the incoming molecules and therefore generates no entropy to operate. This case is different from the spring-operated Maxwell demon on the right side of the above figure, which allows through only those molecules fast enough to open the door against the spring. This may not be too far-fetched: it has become known recently that nanomaterials behave anomalously where the Second Law is concerned, probably due to their microstructure. But even the microscopic sorting door falls under the curse of the second Law. That tiny spring, indeed, would end up taking some of the energy of the incoming molecules, with the result that the door would end up shaking so badly that soon it would not be able to classify the molecules at all. But a membrane with simple holes would not take any more energy than a wall without holes. The wall material can be perfectly rigid, and still it would fulfill its mission to restrain novium safely to one side of it. Molecules too large to pass through would bounce off elastically, while those that pass need not lose any energy as they do so.

Still, our instinct tells us that there must be a reason why this machine cannot work, or the world might go upside down. Consider this: the gas in the expansion chamber does not need to be completely absent from the environment for the machine to produce power; it only needs to be rare enough so that producing it takes less power than it gives when it expands, according to eq. (4). An inventor might speculate on what gases are easy to make but are rare outside, but let us just look at carbon dioxide, for instance. Pure CO2 can be generated by a number of processes well known to freshman students, (such as dripping vinegar on marble), none of which take much energy at all. Yet, the mole fraction of CO2 in earth’s atmosphere is only 0.0003, yielding, from eq. (3), 456.6 kJ per kg of pure CO2 in the expansion chamber, if the temperature is the standard 25ºC. Once liberated, the CO2 is captured back into rocks by biotic processes, so ultimately the power produced by the machine has come from the sun. Is this, therefore, a perpetual motion machine, or isn’t it?

But perhaps this example—though possibly the basis for a power-producing method—only serves to muddy the issue, which is whether the laws of Thermodynamics can allow the infinite exergy case. Perhaps the problem is that the law of Thermodynamics that prevents this perpetual motion machine from working has not yet been promulgated, and therefore the machine would keep happily working, oblivious to any fault or misdemeanor.

The Third Law exists already, so the new law (if God decides to pass it) would have to be called the “Fourth Law” at best. It might read like this:

“It is impossible for the exergy of any system to be infinite.”

Or, more specifically:

“It is impossible for the concentration of any substance to be zero.”

In its second form, the Fourth Law smells suspiciously like Schrodinger’s cat, which is both dead and alive at the same time. In our case, the undead “novium” has acquired the ability to tunnel, ghost catlike, through any wall, so that it is on both sides of it at the same time. There was always a certain amount of tunneling, controlled by Heisenberg’s principle, but now we are imposing a minimum value: there must be at least enough tunneling so that this cat’s exergy drops below the power it takes to make it.

But maybe God will be happy with this loophole: the “novium” in our machine won’t the same in every stroke, and therefore the machine isn’t strictly running in cycles. In that case, he might let us keep running it to produce infinite power as long as we don’t fill this universe with our creations (such as the different kinds of novium). And then, we’ll finally be able to say (in a rather subdued voice, just in case):

Eppure si muove!

PassLok in the UK

david-cameronIt is already illegal for a Briton to refuse to surrender his/her/its password to law-enforcement authorities, and Prime Minister Cameron is now trying to make all non-backdoored encryption illegal as well. What can you do if you are affected by this situation?

My answer, as you have already guessed, is: use PassLok.

Actually, it’s not only UK citizens who have this problem. This article explains how you may be in the same boat if you happen to live in France, India, Australia, and other places. But let’s say you are a Briton.

There are five reasons why you should use PassLok rather than other solutions to secure your email (besides being much simpler, and prettier too):

1. No servers or storage. Since nobody stores your data or keys, nobody can get an order to surrender them. In PassLok, your secret Key is never stored anywhere, no even on your trusted devices, which you may be forced to produce and unlock at law enforcement’s more or less kindly request. You lock your data with PassLok, and it is in this form that they get transmitted through your separate email program. The email provider will produce your locked data if pressured to do so, but not the Key that unlocks it because they don’t have it. The only place where that Key resides is in your head.

2. Decoy mode. But let’s say it’s illegal for you to refuse to surrender this precious Key. Then go ahead and give it to them, so long as you use PassLok’s Decoy mode. In this mode, locked items actually contain two plaintext messages, one of them completely undetectable. This way, people can be carrying a conversation through the main messages, and an entirely different one through the hidden messages, locked under a different set of Keys. Should they be forced to surrender their Keys, the hidden messages remain secret and just as undetectable. It would be unreasonable for any authority to demand the surrender of a second Key that, most likely, doesn’t even exist.

3. Perfect Forward Secrecy (PFS). PassLok is probably the only application meant for asynchronous communications such as email (this means that both parties are not necessarily online at the same time) that implements PFS. When PFS mode is used, locked messages become unlockable when the next message is exchanged, because the Keys used for locking are overwritten on the device and are not stored anywhere else. This way, if one is forced to surrender his/her/its secret Key, past messages cannot be unlocked no matter what. If this is not enough, PassLok has Read-once mode, where Key deletion happens as soon as a message is read, resulting in the closest thing to self-destruction this side of the Great Firewall of China.

4. Steganography. This is the Greek name for the science of hiding. If you live in China (or the UK in the near future), you might get in trouble just for emailing random-looking encrypted messages. Unlike pretty much all other programs, PassLok offer you the opportunity to transform its random-looking output into apparently normal text taken from a user-selectable cover text, which the recipient can return to its original state before unlocking it. PassLok also includes two ways to hide its output into images, which can then be sent as attachments to email messages. Images can hide a lot of data.

5. PassLok is human-readable. Britain and other countries with democratic leanings have laws protecting free speech (which, rather inconsistently, doesn’t always extend to cryptography). Well, the possession and distribution of at least the html version of PassLok should be protected under those laws because PassLok is human-readable code, not machine code. This is precisely how PGP survived the onslaught of the US Government back in the 1980’s, when its developer began to distribute it as a book containing the source code, which people could then type or scan and compile to executable code. PassLok is used directly in this form, simply by loading it into a browser.

Modified interlock protocol for authentication

Of the many difficult problems dealing with public key cryptography, there are few so hard to crack as public key authentication. Public keys are easy to obtain (that’s why they are “public”), and because of this, it is hard to be sure that a certain key belongs to a certain person, what is known as authentication. Usually it is recommended that the key be handed out in person or that it be identified (directly or through a one-way hash) by a rich communication medium such as voice or video.

But sometimes it might be possible to do it strictly by email, even though you suspect someone might be watching. Read on for details.

If you cannot make contact with the other person through a rich channel such as voice or video, you’re going to have to start using somebody’s public key without knowing for sure if that public key is genuine. Trust will build up gradually, as the messages sent back and forth serve to confirm the identity of the participants. But there are ways to discover if a public key is fake with only a few messages traveling back and forth.

The easiest thing to do is to send a message to the public key owner, including a question whose answer only the two of you know, and asking him/her to send you his/her public key, encrypted with a symmetric key that is the answer to that question. If the answer is correct, you’ll be able to decrypt the message, and thus retrieve the genuine public key (which should match the one you have). An interloper who is watching and perhaps modifying your traffic won’t be able to decrypt the message in order to change it, and thus he/she must be content with preventing you from getting that message, in which case you’ll know the public key in your possession have is fake.

But the easy way has the problem that the other person’s answer must be exactly the answer I know, down to the smallest spelling detail, or the message won’t decrypt. There is another way to authenticate a public key using a variation on the “interlock protocol,” which admits answers that don’t have to be exact. It is enough if the persons asking the questions can recognize the answers as valid in a more general sense.

This protocol is based on the “interlock protocol,” first described by Rivest and Shamir in this paper. In essence, people encrypt messages but only send half, and wait to get the other person’s first half of a reply before sending out the second half. This causes a “man in the middle” a big headache because, since he cannot decrypt half an encrypted message, he needs to make up messages to keep the exchange going, or his cover is blown. Unfortunately, it has been shown that this protocol can be defeated by a particularly clever interloper, using this method. Does that mean that the interlock protocol is no good? Far from it. What’s needed is extra cleverness in the way it is set up. As a clever user says in this posting, the key lies in asking questions that require an answer.

So here ‘s the way you can set up a slightly modified interlock protocol in order to authenticate a public key. Since the following is extracted from the manual for PassLok, which uses non-standard nomenclature for the sake of novice users, let’s get that out of the way first. In PassLok, a public key is called a Lock, and a private key a Key. A digital signature is a Stamp, and a one-way hash is an ID. Encrypting is referred to as “locking” and decrypting as “unlocking”.

With that clarified, let’s look at this exchange between Alice and Bob:

1.     Alice obtains her friend Bob’s Lock, but she fears that it might be counterfeit and someone else might be unlocking the messages she sends to Bob, reading them, perhaps changing them, and then re-locking them with Bob’s actual Lock for him to read. So Alice sends Bob this email:

“Dear Bob. I just got your Lock for the app called PassLok from your email signature. I fear that I’m under surveillance, so it’s very important that I make sure that this Lock actually belongs to you. Here’s what I want you to do:

a.      Write a question whose answer only the two of us know, and lock it with my Lock, which is included at the bottom of this email. Then split it in two parts and send me the first part. I’ll be waiting for it.

b.     When I get it, I’ll send you the first half of a similar question, which has been locked with your Lock. When you get it, send me the second half of your locked question.

c.      When I get that, I’ll send you the second half of my question, and also the answer to yours, which then I’ll be able to read. I’ll send the answer locked with your Lock.

d.     If I answered your question correctly, put together the two halves of my question and unlock it. Then write the answer, lock it with my Lock, and send it back to me. Then I’ll know that your Lock is authentic. Your friend, Alice.”

2.     When Bob gets this, he decides it’s going to be fun to do all his, and writes a question whose answer only Alice knows, locks it with her Lock, which was appended to her email, splits the locked message into two parts, and sends Alice the first half.

3.     Alice gets the first half, and writes her question to Bob. Then she locks it with Bob’s presumed Lock, but only sends him the first half. Because nobody can unlock half a message, she must wait to get the second half of Bob’s message in order to answer his question.

4.     Bob gets the first half of Alice’s locked question, and he sends her the second half of his locked question.

5.     Alice gets the second half of Bob’s question. Now she can put the two halves together and unlock them with her Key. She writes a message answering Bob’s question, locks it with Bob’s presumed Lock (no need to split it now), and sends it back to him along with the second half of her question to Bob.

6.     Bob gets Alice’s email and can now unlock both messages from her. He sees the correct answer to his question in the first one, so he unlocks the one containing Alice’s question. He writes the answer, locks it with Alice’s Lock, and sends it to her. Had he been unable to unlock Alice’s question, he would have told her so. If her answer to his question was wrong, he would have told her, too.

7.     Alice gets Bob’s message, unlocks it and, seeing the correct answer to her question, is satisfied that Bob’s Lock is authentic. Otherwise she gets a message from Bob telling her that things didn’t work out, or something other than a message answering her question, or nothing at all, and she decides that “Bob’s Lock” was bad.

An alternative to splitting locked messages is to make the ID of the locked or unlocked message and send it ahead of the message itself, or apply a Stamp to the message and send the Stamp ahead of the message. The recipient will then check the ID or Stamp after the message is received, and will know that something’s wrong if it is not the same. Another option is not to lock the answers to the questions, in steps 5 and 6, since authentication also works if those messages are not locked; locking just preserves those answers, which might be sensitive, from a less-than-powerful eavesdropper who might see the exchange.

If Alice does not know Bob well enough to be able to ask him a question whose answer is known only to the two of them, or maybe Bob doesn’t know Alice well enough to ask a similar question, there is still something they can do, so long as Alice can recognize Bob in some way, and Bob can recognize Alice. Instead of a personal question, the asker can direct the other person to simply repeat something contained in the “question” message, but to do so in a video or audio recording, which is then put somewhere in the cloud, and the URL is sent back as an answer. The asker will then see or hear the other person, whom he/she recognizes, saying something that she/he would not be saying unless she/he has read the question message.

Let’s see how this protocol foils Mallory, who is able to intercept and modify their communications without them knowing anything. He poses as Alice before Bob, and as Bob before Alice. In this case, Alice does not have Bob’s genuine Lock, but one that Mallory made in order to impersonate Bob. Likewise, Bob does not get the Lock that Alice sent in step 1, but one for which Mallory has the Key.

Things begin to go wrong for Mallory in step 3. Since Mallory cannot yet read Alice’s question but nevertheless has to send something to Bob to keep the exchange going, he must send him a question from “Alice” that likely has nothing to do with the question the real Alice has asked. That, or pretend in step 2 that Bob is refusing to go along with the game, which is not going to do much to reassure Alice.

Mallory will then get the whole question from Bob, so he will be able to unlock it, re-lock it, and pass it along to Alice in step 4, and then get from her a reply that will satisfy Bob in step 6. But the damage has been done. Mallory is committed to sending Bob the second half of a question from “Alice” that is most likely not the question the real Alice asked, or otherwise Bob won’t be able to unlock the message, and Mallory’s cover will be blown. Bob might not discover the ruse at this point, but it is highly unlikely that his answer, or whatever else Mallory can come up with to replace it, will satisfy the real Alice’s question. Then she’ll know someone’s in-between and Bob’s Lock is not authentic.

If now they repeat steps 2 to 6 all over with one new question from either side, but this time with Alice asking the first question, Bob will also notice that something is wrong. But what if there is no Mallory, and “Bob’s Lock” was not being used to listen in but was simply corrupted or mistaken for another Bob’s Lock? Then Bob will simply be unable to unlock Alice’s question in step 6, and he will alert her of that fact. It is possible that a Mallory could still be watching without attempting to modify the messages passing through him unless he really has to, but it is unlikely that he could replace Bob’s announcement that the protocol failed with something that would satisfy Alice, because at that stage Alice won’t accept anything but a correct answer to her question, or she will decide that “Bob’s Lock” is bad.

It took some homework and three emails from each side, after which they still don’t know each other’s authentic Lock (which would be impossible with Mallory changing everything, anyway), but Alice has avoided being duped by an enemy.

Lessons from the VIC cipher

abelIn the mid-1950’s, the Soviet spy Reino Hayhanen, codenamed VIC, and his handler Rudolph Abel (in the picture) pulled off an incredible feat: they utilized a paper-and-pencil cipher that not even the FBI (the NSA wasn’t operating within US borders back then) was able to crack until Hayhanen defected and explained its inner workings. Computers already existed, and they were used primarily to crack ciphers like VIC. In this article, I go over some of its features, and how they can be used to enhance other simple ciphers. Read More

Aphid cipher

aphidAphids are those pesky green bugs that eat the plants in your garden. But here the name designates a high-security paper-and-pencil cipher similar to Restonia, based on a couple ciphers that are more than a hundred years old.

Aphid derives from the “bifid” cipher invented by Philip Delastelle in 1895, to which it adds an extended columnar transposition step. Bifid was never used in practice despite its excellent properties, but its inner design influenced cryptography in a profound way, so that today’s computer-based symmetric encryption algorithms are a longer, more complex implementation of the same basic ideas: fractionation and diffusion. Fractionation means that every plaintext character is broken apart into several pieces, and diffusion means that the pieces are sent to different spots on the ciphertext, where they might be recombined into something else. Unfortunately, the original bifid cipher was easy to break because the plaintext pieces were sent to predictable locations, which makes it possible to reconstruct the original before encoding, at which point it can be solved like any monoalphabetic cipher. Like all ciphers devised before the computer age, bifid also suffered from short keys, liable to be found by exhaustive brute-force trial of all possible combinations.

Another classical cipher in Aphid’s family is ADFGX, which actually saw use during World War I on behalf of the German army. This cipher also used a 5×5 Polybius square for its substitution step, and then it had a simple columnar transposition. ADFGX was soon broken, however, because a single transposition does not really obscure the plaintext very much. We know now that just a double transposition is much better. In addition, there was no recombination of the 2 parts made from each plaintext letters, which wasted much of the potential of fractionation. Still, cryptanalysts were only able to break it on days of great traffic, when operators got overwhelmed and began reusing keys for a large number of messages, some of them with stereotyped contents known to the Allies.

In order to strengthen bifid and ADFGX into a derivative that can resist modern computer-aided cryptanalysis, we are going to follow a similar approach as in the Restonia cipher, where transposition based on a long passphrase is combined with substitution into digits based on a straddling checkerboard. The main difference between Aphid and Restonia is that Aphid uses a “Polybius square” substitution rather than a straddling checkerboard, and that the encoded result is converted back to letters at the end of the whole process. To illustrate the instructions, we will encipher “MEET ME AT THE STATION MONDAY AT 5 PM” using the passphrase “secret code” (too short, but will serve for illustration purposes) as the serial “ABC”. These are the steps:

  1. 1. Serial code (optional). In order to prevent multiple anagramming attacks, which are possible when two messages of the same length are encrypted with the same key, it is a good practice to use a different serial code for each message. The length of the serial code depends on how many messages will be exchanged. Three characters are good enough for a few hundred messages. For our example, we will use “ABC” as serial.
  2. 2. Code generation. Two codes are made from the passphrase and the serial: one for encoding the plaintext by substitution, and the other for scrambling the encoded result.
  3. The easiest to make is the scrambling code: just number each word in the serial + passphrase, according to their order in the dictionary; if a letter is repeated, begin from the right (for better scrambling). If a word contains less than four letters, which would lead to insufficient scrambling, merge it with the next one before finding the order. For the serial + passphrase “ABC” + “secret code” = “abcsecret code”, this results in: “124863759,1423”
  4. The encoding table is made into a 5×5 “Polybius square”, which contains the letters of the alphabet (J is combined with I). We fill it this way:
  5. Take the passphrase and place each new letter you find, in sequence, on the first row beginning from the left, and continuing on the other rows as needed. This is the first partial table in our example :
1 2 3 4 5
1 S E C R T
2 O D
3
4
5
  1. Now fill the table with the rest of the dictionary in reverse order, for better security. This is the result:
1 2 3 4 5
1 S E C R T
2 O D Z Y X
3 W V U Q P
4 N M L K IJ
5 H G F B A

To ease the encoding of long messages, this can also be expressed as an alphabet, with the coordinates for each (table,row,column) written below each letter:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
5 5 1 2 1 5 5 5 4 4 4 4 4 4 2 3 3 1 1 1 3 3 3 2 2 2
5 4 3 2 2 3 2 1 5 5 4 3 2 1 1 5 4 4 1 5 3 2 1 5 4 3
  1. 3. Encoding. Now we convert our plaintext into a numerical code. Below each plaintext letter we write vertically the two-digit code for each letter. In order to write numerals, we’ll write “X”, followed by two digits for each figure according to the following table (in the text, we’ll write “X” as “CS” or similar), and the code “55” at the end of the digits. The rest of the codes can be used for punctuation signs, etc.:
1 2 3 4 5
1 1 2 3 4 5
2 6 7 8 9 0
3 . , etc.
4
5 end

Here’s the result of encoding:

MEET ME AT THE STATION MONDAY AT X5end PM
4111 41 51 151 1151424 424252 51 215   34
2225 22 55 512 1555511 211254 55 455   52

If we want the final result to be a certain length—perhaps in order to disguise it as something else—this is the place to add as many gibberish pairs as needed, usually at the end of the text.

  1. 4. Scrambling. The numerical code is now scrambled with each code we obtained earlier. To do this, we first write the first scrambling code, and then underneath it we write left to right by rows the code we just obtained in the previous step, starting from the first row, then the second row, then the third. Then we read the scrambled code vertically, beginning with the column marked as “1”, then “2” and so on until the end. Then we scramble the result in the same way with the second scrambling code, and so on until there are no more scrambling codes. For our example, we obtain these two tables, whre the top row in both cases is the scrambling code:
1 2 4 8 6 3 7 5 9
4 1 1 1 4 1 5 1 1
5 1 1 1 5 1 4 2 4
4 2 4 2 5 2 5 1 2
1 5 3 4 2 2 2 5 2
2 5 5 5 1 2 1 5 5
5 5 1 1 2 1 1 2 5
4 5 5 4 5 5 5 2

Result read off by columns in the given sequence: 4541254 1125555 1122215 1143515 1215522 4552125 5452115 1124514 142255

1 4 2 3
4 5 4 1
2 5 4 1
1 2 5 5
5 5 1 1
2 2 2 1
5 1 1 4
3 5 1 5
1 2 1 5
5 2 2 4
5 5 2 1
2 5 5 4
5 2 1 1
5 1 1 2
4 5 1 4
1 4 2 2
5 5

Result read off by columns in the given sequence: 4215253155255415 445121112251112 115114554141242 5525215225521545

  1. Decoding. We write this code into two rows of equal length, filling one row at a time, and find the corresponding letters in the Polybius square by reading from top to bottom, taking the upper figure as row and the lower figure as column. This is the result (here we leave numerical shifts alone, if encountered, without trying to shift into numbers and special characters):
4 2 1 5 2 5 3 1 5 5 2 5 5 4 1 5 4 4 5 1 2 1 1 1 2 2 5 1 1 1 2
1 1 5 1 1 4 5 5 4 1 4 1 2 4 2 5 5 2 5 2 1 5 2 2 5 5 2 1 5 4 5
N O T H O B P T B H Y H G K E A I M G E O T E E X X G S T R X

So the final result, which we can transmit by insecure channels, is this preceded by the serial:

ABCNO THOBP TBHYH GKEAI MGEOT EEXXG STRX

Decryption is roughly the reverse of encryption. This way:

  1. 1. Retrieve the serial (if any) from the beginning of the ciphertext.
  2. 2. Code generation. This step is identical to step 2 for encryption, starting from the serial and the passphrase.
  3. 3. Encoding. This is the reverse of encryption step 5. We find the 2-digit codes for each letter in the ciphertext and write it in two rows underneath, then we read it off by rows, to be descrambled in the next step.
  4. 4. Descrambling. This is the reverse of encryption step 4. We begin making a table for the last scrambling code, with as many columns as digits in the code. The number of rows is the numerical ciphertext length divided by the code length, rounded up. The remainder of the division tells us how many cells in the last row should be blanked out. Then write the ciphertext numbers from top to bottom, starting on column 1, then 2, and so forth, filling all active cells in each column. The resulting table should be identical to the last scrambling table made when encrypting, but this time the result will be read off horizontally from the top, left to right. Then the result will be written in columns on a table made for the second-last scrambling code, and so on until the first scrambling code is used. The final result read by rows is the encoded plaintext, which we divide into two equal rows.
  5. 5. Decoding. Now take the encoded plaintext and decode it back to letters (and numbers, if any) where the top number is the row and the bottom number the column in the Polybius square, thus reversing encryption step 3.

This cipher shares many features with the Restonia cipher, but in a different way. Fractionation and diffusion are better because every plaintext letter gets split into two pieces, and the pieces are sent to distant spots within the ciphertext where they recombine to form letters that are most likely different from those in the plaintext. Aphid doesn’t take into account expected plaintext frequencies as Restonia does, but the combination of fractionation and scrambling is very effective to destroy any language-derived statistics present in the plaintext. All the properties having to do with the scrambling are the same as for Restonia, and there are two additional column to row shuffles (one when encoding to numbers, and one when decoding back to text), which come for free with the Polybius encoding. Fractionation can be made even stronger by using a 3x3x3 “Polybius cube” rather than the 5×5 square, and using three-digit codes for all letters. This is what Delastelle’s “trifid” cipher, an evolution of bifid, did back then. The problem is that, having only three different values for the encoded digits, we end up with long, tedious repetitions, and the likelihood of mistakes becomes much greater.

Unlike with the Restonia cipher, the last decoding step is necessary in order to collect the diffusion effect and transform each plaintext letter into two different letters in the ciphertext. Because of this, Aphid encryption and decryption takes a little longer than Restonia, but its theoretical strength is greater due to the more complete diffusion of the plaintext. Check it out and compare it with Restonia, and see which one you like better. I use Aphid when I want the end result to be letters, Restonia when I want it to be numerals.

Just about everything said about attacking the Restonia cipher can be said about Aphid. The main difficulty lies in having to descramble a code whose alphabetic conversion isn’t known. The ciphertext before conversion back to letters contains very few different characters, so that any type of frequency analysis is bound to fail. Frequency analysis would be effective once those have been (correctly) encoded as letters, but this cannot be done before the number codes are descrambled. Anagramming will fail form the same reason: there’s too few different numerical characters to be able to eliminate unlikely solutions. Many grammatically correct solutions are possible for a given ciphertext if one only has to descramble the figures and convert them back to letters. For a typical five-word passphrase (around 60 bits of entropy), the “unicity distance” for English plaintext is 60/3.5 = 17.1. This means that a ciphertext consisting of 17 or fewer characters would be theoretically impossible to crack, no matter how much computational effort is put into it. Which doesn’t mean that longer texts would be easy to crack, either.

The classical method used to crack ADFGX won’t work with Aphid for two reasons: 1, there will normally be more than one scrambling step, which is way better than one, and 2, the final decoding back to letters effectively obfuscates any language-dependent frequency that might have remained, which was needed in order to break ADFGX. In this regard, Restonia still suffers from this weakness, which is only patched up (quite effectively, though) by the fact that the straddling checkerboard used in the initial substitution messes up the most important letter frequencies.

How about using methods for attacking Delastelle’s bifid cipher? In essence, the conventional attack tries first to determine the “period” of the cipher (bifid converts columns to rows by blocks of a certain size) by evaluating certain statistics on the ciphertext. When the period is known, descrambling of the blocks can be done immediately, and then what is left is a digraphic substitution involving a single alphabet, which is readily solved by standard frequency analysis. But this will not work for Aphid because the blocks are not predictably scrambled and, in fact, the whole text is a single block. The closest thing to a “period” to be determined is the number of columns of each scrambling step, and there are several of them all mixed together. Unless the passphrase was very badly chosen, the Aphid “period”, resulting from all the scrambling steps, will likely be longer than the ciphertext length.

I believe Aphid and Restonia are actually stronger than the famous Enigma code, which the Germans used during World War II and was the first routinely cracked with the help of the first digital computers. It was quite an epic effort, nicely rendered in the 2014 film “The Imitation Game.” Enigma was essentially a stream cipher based on a mechanical pseudo-random number generating machine. Aphid and Restonia are block ciphers operating on the full message length. Even today’s digital block ciphers, such as AES, don’t operate on full-message blocks, but on fixed-length blocks, and they use fixed substitution and permutation operations, while in Restonia and Aphid, they are key-dependent.

Their superior resistance to cryptanalysis of modern ciphers lies in the fact that another substitution is made before each permutation, and several “rounds” including a substitution and a permutation are performed before the final ciphertext is produced. As a result, each character in the plaintext ends up influencing every character in the ciphertext, in ways that depend nonlinearly on the key. Aphid is meant to be simple enough to do with pencil and paper, so that the number of operations is reduced to the minimum necessary while providing as much diffusion as possible, which is two positions per character. Its superior strength relative to bifid and other classic ciphers lies primarily in its ability to use arbitrarily long keys, having a much larger entropy, so it stands a chance against computer-aided cryptanalysis.

Restonia cipher

492px-Smaller_Coat_of_Arms_of_Austria_(1815).svg (1)Paper and pencil ciphers are fun and can be useful in a pinch, when all computers around are suspect. In a previous article, I presented “Root,” a cipher that gives decent security and only requires a dumb calculator. In this article, we’re going to try and do the same without even that. Only paper and pencil. And you don’t need to learn Restonian.

“Restonia” is a cipher evolved from the VIC cipher used during the Cold War. The VIC cipher is called this way because its user, Reino Häyhänen, was a Russian spy with code name VICTOR. Even though it is a paper and pencil sort of cipher, the NSA was not able to crack it from 1953 until 1957, when Reino defected to the West. There is an excellent Wikipedia article on this cipher.

Now, the VIC cipher would be cracked easily today because its key was too short. This is a problem shared with just about very classical cipher before computer came in the scene, with the exception of one-time pads. Ever since a team of volunteers cracked the 56-bit DES cipher in less than 22 hours by simple brute-force trying of every possible key, we know that key length needs to be pretty long in order to withstand a computer-supported attack. The problem with long keys, though, is that they are hard to remember.

Unless some mnemonics are used. Dictionary words, for instance, have a minimum of 13 bits of entropy per word, on the average. Thus, a phrase containing just five words has roughly 65 bits of entropy, which in principle is 29 = 512 times harder to brute-force than DES. Phrases with five or more words are still easy to remember. Some examples: “I’ll have the chicken soufflé with fries,” “Don’t tell me you got fired,” “I love the smell of napalm in the morning,” just to mention some possibilities.

The trick is how to turn a longish set of words into a usable encryption key, and how to use such a key in a pen-and-paper cipher. Well, after thinking about it for a while and looking at the lessons of the past—many can be found on Wikipedia, practicalcryptograhy.com, and Kahn’s classic history “The Codebreakers” unabridged version—a new chiffre indechiffrable has been produced, codenamed “Restonia.” This is the name of a hypothetical small country where most children grow up to be spies. The name happens to contain the most frequently used letters in English (and most Latin-character languages, for that matter).

BTW, everything I’ve said so far also applies to the very similar Aphid cipher, which you can also find on this blog. Aphid is more secure because it has a larger degree of plaintext diffusion, but it is also more tedious and takes one extra step. Your pick. Back to Restonia.

Encrypting involves three obligatory steps, plus a couple optional steps. We are going to illustrate the method by enciphering “MEET ME AT THE STATION MONDAY AT 5PM” using “secret code” (too short, but will serve for illustration purposes) as passphrase and serial “123.” These are the steps:

  1.    Serial number (optional). Security is enhanced if each message is given a different serial number, which is never reused (at least for messages of equal length). A three-digit serial will allow us to encrypt hundreds of messages with one passphrase. Let the serial number for our example be “123.”
  2.    Code generation. Two codes are made from the serial + passphrase: one for encoding the plaintext, and the other for scrambling the encoded result.
  3. The easiest to make is the scrambling code: just number each word in the serial + passphrase, according to their order in the dictionary, taking into account numerals that may already be contained in the serial (which is pre-pended to the first word). If a word contains less than four letters, which would lead to insufficient scrambling, merge it with the next before finding the order. If a letter or number is repeated, begin from the right, for better scrambling. For the serial “123” and passphrase “secret code” = “123secret code”, this results in: “123 864759,1423”
  4. The encoding table is made into a 3×10 “straddling checkerboard,” which contains the letters of the alphabet, plus a catch-all symbol for punctuation, and a numbers shift. The first row contains only high-frequency letters (coincidentally, those in the name “Restonia”), with two spaces blanked out. The other two contain the rest of the alphabet, etc. We fill it this way:
  5. Take the passphrase and count the number of letters in the first two words that have different lengths (don’t merge them with the next even if they are short; if they are all equally long, go up by one for the second digit) = 6,4. Consequently, blank out cells 6 and 4 on the first row.
  6. Take the passphrase again, and place each new letter you find, in sequence, either in the first row if it is part of “restonia” or in the second and third, beginning from the left. This is the result in our example:
S E R blank T blank O
C D

iii.     Now fill the rest of the table this way: Top row, the rest of the letters in “restonia”, in reverse order (for less predictability). Rest of rows, the special characters, followed by the rest of the dictionary, also in reverse order. This is the result with labels added at top and left:

1 2 3 4 5 6 7 8 9 0
S E R blank T blank O A I N
6 C D # Z Y X W V U
4 Q P M L K J H G F B

The top labels are just the digits 1 to 0 in sequence, those on the left, starting with the second row, are the lengths of the first two words of the passphrase (consecutive, if all words are equally long). This is our straddling checkerboard.

  1. Encoding. Now we convert out plaintext into a numerical code. The letters on the first row of the checkerboard are replaced by the single digit above them. The letters and symbols on the other two rows are replaced by two digits: the one on the left, followed by the one above. If punctuation is needed, use the special character. To represent numerals, enter the numbers shift symbol, then the straight numeral, and end with two number shifts. Here’s the result:
M EETM EATTH ESTATIONM OND AY AT# 5# # P M
4322543285547215859704370628668564564644243

If we want the final result to be a certain length—perhaps in order to disguise it as a list of phone numbers or whatnot, more on this at the end of the article—this is the place to add as many gibberish digits as needed, usually at the end of the code.

  1. Scrambling. The numerical code is now scrambled with each code we obtained earlier. To do this, we first write the first scrambling code, and then underneath it the long numerical code we just obtained in the previous step, left to right row by row. Then we read the scrambled code vertically, beginning with the column marked as “1”, then “2” and so on until the end. Then we scramble the result with the second scrambling code, and so on until there are no more scrambling codes. For our example, we obtain these two tables:
1 2 3 8 6 4 7 5 9
4 3 2 2 5 4 3 2 8
5 5 4 7 2 1 5 8 5
9 7 0 4 3 7 0 6 2
8 6 6 8 5 6 4 5 6
4 6 4 4 2 4 3

Result: 45984 35766 24064 41764 2865 52352 35043 27484 8526

1 4 2 3
4 5 9 8
4 3 5 7
6 6 2 4
0 6 4 4
1 7 6 4
2 8 6 5
5 2 3 5
2 3 5 0
4 3 2 7
4 8 4 8
5 2 6

Result: 44601252445 95246635246 8744455078 53667823382, which can be transmitted out as is, preceded by the serial: 1234460125244595246635246874445507853667823382.

Decoding (optional). Sometimes we may want to transmit letters rather than decimal digits. The simple way to do this would be to just use the checkerboard to get the letter equivalent of the result, but this would cause many of the letters to go back to plaintext, which is bad. Therefore, we will be a little more devious and before decoding back to letters we’ll multiply the numerical ciphertext (without the serial) by the number of letters in the last word of the passphrase, up to 9. If the number of letters is 10 or more, take the last digit. If this last digit is 0 or 1, take the second-last word instead, and so on. If for all words we get 0 or 1, multiply by 7 instead. If the last number requires one more digit after (6 or 4 in our example), double it up and then add ‘XX’ at the end of the output. If the first digit is 0, pre-pend a 0 to the multiplication result before decoding. Then put the serial at the beginning and send it. Here’s what we get for our example:

Numerical code  4460125244595246635246874445507853667823382
Multiplied by 4 17840500978380986540987497782030414671293528
Decoded SOAB TNNIOARANIAZ B IAOF OOAENRNQ J OSEIRTEA
Sent 123SO ABTNN IOARA NIAZB IAOFO OAENR NQJOS EIRTE A

Decryption is roughly the reverse of encryption. This way:

  1. Code generation. First get the serial from the ciphertext and use it in combination with the passphrase to generate the straddling checkerboard and the scrambling codes as described above. This step is identical to step 2 for encryption.
  2. Encoding (optional). This is the reverse of encryption step 5. If the ciphertext consists mostly of letters, we’ll need to get that into a numerical code using the straddling checkerboard. Then we figure out the multiplier from the passphrase (length of last word) as above, and divide the numerical code by it. It should be an exact multiple, otherwise there is an error.
  3. Descrambling. This is the reverse of encryption step 4. We begin making a table for the last scrambling code, with as many columns as digits in the code. The number of rows is the numerical ciphertext length divided by the code length, rounded up. The remainder of the division tells us how many cells in the last row are active, and the rest should be blanked out. Then write the ciphertext numbers from top to bottom, starting on column 1, then 2, and so forth, filling all active cells in each column. The resulting table should be identical to the last scrambling table made when encrypting, but this time the result will be read off by rows from the top, left to right. Then the result will be written in columns on a table made for the second-last scrambling code, and so on until the first scrambling code is used. The final result is the decimal-encoded plaintext.
  4. Decoding. Now take the encoded plaintext and decode it back to letters (and numbers, if any) using the checkerboard, thus reversing encryption step 3. If gibberish digits were added, they will usually decode to gibberish so it’s easy to spot them and ignore them.

The strength of this cipher lies in several features:

  1. Fractionation and diffusion: many letters are split into two-digit codes, and then the digits are separated widely at the scrambling step. High-frequency letters are converted into low-frequency ones by combining with separated digits. This makes it very difficult to do any kind of frequency analysis on the ciphertext.
  2. Compression: often-used characters (r,e,s,t,o,n,i,a) are transformed into shorter codes than less-used ones. This tends to flatten the frequency distribution and helps to keep the ciphertext within the bounds given by the “unicity distance” (keylength in bits divided by 3.5, for English), which is the ciphertext length below which it is theoretically impossible to ever decipher the message without the proper key because it can be deciphered to other equally possible plaintexts.
  3. Mechanization: the process can be done quickly on paper without having to think much. In fact, computer-based encryption algorithms usually do something very similar: break characters into bits that are then scrambled according to the key.
  4. Irregularity: there is no fixed length for any scrambling operation, which makes it hard to attack by simple anagramming. The overall length of the passphrase cannot be easily guessed from the result of the scrambling even if the plaintext is known.
  5. Unlimited key: arbitrarily long passphrases can be used, each word adding more complexity to the scrambling process and more diffusion to the characters. It is like writing on a piece of dough that gets repeatedly kneaded according to each word of the passphrase.
  6. Independence: the way the passphrase material is used for making the checkerboard is quite different from the way it is used for making the scrambling codes. The scrambling codes only depend on the ordering of the word letters, not on the letters themselves. The letters matter when making the checkerboard, beyond their alphabetical order. Therefore, there is little danger that one operation would undo the other, even partially, and so it is safe to use the same passphrase as a starting point for both (except for a few very bad choices, which should be obvious to the user right away).
  7. Reusability: since the scrambling operation with irregular key fragments is hard to reverse, there is little danger that the passphrase be recovered from plaintext samples and their corresponding ciphertexts. Still, it is a good practice to include a serial number that never gets used again with the same passphrase, since messages of identical length scrambled with identical scrambling codes are subject to the anagramming attack.

 

Now let’s put on our hacker’s hat and try to crack this baby. The algorithm has been published on this blog, so this is not a secret. The secret is the passphrase and the plaintext. We have the numerical ciphertext from step 3 above: serial 123 + 44601 25244 59524 66352 46874 44550 78536 67823 382. These are the digit frequencies:

digit 1 2 3 4 5 6 7 8 9 0
occurrences 1 5 4 9 7 6 3 4 1 2

Since in English the most frequent letters go in this order: e-t-a-o-i-n-h-r, we might feel tempted to say 4=e, 5=t, 6=a, which would be incorrect because 4 and 6 are actually used for the least-frequent letters. Or, taking this into account, we might say 6=e, 3 or 8=t or a, which ends up being correct only in the guess for “a”. The problem here is that the low frequency letters are summing their frequencies because of the straddling checkerboard method, thus putting them on a par with the high-frequency letters, thus making frequency analysis almost useless.

Let us now look for digraphs and trigraphs. We see “44”, “46” and “52” three times which, knowing the encoding, could be interpreted as “L”, “J”, and “TE” respectively. None of them are actually present in the plaintext. All the frequent digraphs are artifacts resulting from scrambling. There isn’t a single trigraph to sink our teeth into, even though the plaintext is full or repetitions. Clearly a longer piece would have contained some repeated trigraphs, but again it is very likely that they would bear no relationship with the plaintext because they result from figures brought together from very distant original locations.

Normally, a straight transposition cipher is attacked by “multiple anagramming,” which consists of switching characters around in several ciphertexts of the same length that are suspected to be scrambled in the same way. By detecting which permutations maintain “fitness” with the patterns of the language in all ciphertexts, and which don’t, one can eventually descramble all the ciphertexts at once. But our cipher includes a serial number for the express purpose of defeating this technique since not two messages are scrambled in the same way. If the serial was a permutation that was applied near the end, there might be some hope of reversing it first, and then working with the partially de-scrambled ciphertexts, but unfortunately for the cryptanalyst the permutations encoded by the serial number are the first to be applied when scrambling, and the last when descrambling. Additionally, there are more sophisticated attacks based on dictionaries or “hill climbing,” but these are still based on fitness measures, which are obscured by artificially enhancing the probability of low-frequency letters by means of the straddling checkerboard.

A similar cipher used during World War I, ADFGVX, was broken by frequency analysis because the Polybius square method used as a first step did not obscure completely the underlying frequencies of the language. Also, ADFGVX used only one transposition step, which induces considerably less unpredictability than a mere double transpositions.

How about a “known plaintext” attack, where both the ciphertext and its matching plaintext are known? Can we then recover the passphrase, or something like it? This would clearly succeed if only the substitution had been done, for then we could match letters with their codes immediately and thus reconstruct the checkerboard. It would be harder if only transposition had been used because there would be many identical figures in the encoded plaintext competing for each position in the ciphertext, but there would be only so many of these ambiguities, so that eventually the scrambling code could be figured out. If both solution methods proceed in parallel but are independent of each other, they can help one another. The problem is that the solution of one affects the solution of the other, so that we don’t know the starting position of the figures until we know the checkerboard, and we cannot know the substitutions that make up the checkerboard until we know how the numbers move during the scrambling step. The two problems have their difficulty compounded when they need to be solved at the same time.

The diffusion effect is not helping one bit here. Let’s do a quick experiment and switch just two numbers in the first scrambling code (in our example, which involves only two codes), say, the 1 and 2 columns. Then the second scrambling table becomes this:

1 4 2 3
3 5 7 6
6 4 5 9
8 4 2 4
0 6 4 4
1 7 6 4
2 8 6 5
5 2 3 5
2 3 5 0
4 3 2 7
4 8 4 8
5 2 6

Result: 36801252445 75246635246 6944455078 54467823382. As a table, with differences highlighted:

original 4460125244595246635246874445507853667823382
altered 3680125244575246635246694445507854467823382

Out of 43 digits, 8 digits or about 20% have moved to different locations. This is hardly surprising since the first scrambling involved nine columns and two of them were switched, resulting in 2/9 = 22.2% of digits moving to different locations. If the two columns had been switched in the second table (four columns), we would have altered around 50% of the ciphertext. This means that we won’t necessarily know that we are getting close to a solution until we almost run into it. But solution methods invariably rely on some sort of fitness indicator for incomplete solutions, which allows the cryptanalyst to find the plaintext by successive approximations. If the indicator shows no better fitness until the very end of a successful de-scrambling, it becomes very hard to get even started.

It is a lot like walking in the dark to find an exit, except that picking a direction and staying with it until a wall is found, then following the wall until a door appears, is not going to work. There is no wall that we can follow. Instead, it’s more like finding a trapdoor in the middle of a dark field. We won’t know where it is until we’ve almost fallen into it. We might be walking only a few feet away and never know it was there.

A final word on how to deliver the ciphertext. Often it will be desirable to hide the fact that encryption is being used. A ciphertext consisting entirely of decimal digits can be disguised as a list of phone numbers, for instance, or as some sort of statistics. If we want to make the output appear as a series of 10-digit phone numbers, it will be best if the final ciphertext length is a multiple of 10. In order to make this happen, we will add some gibberish digits to the just-encoded plaintext (after step 3) to reach the appropriate length (remember that the serial, if any, is added at the end of the process), which will be scrambled along with the real message. The gibberish digits, which are technically named “nulls” will be easy to distinguish from the plaintext at the end of the decryption process because likely they won’t decrypt as anything meaningful. Nulls make cryptanalysis harder because they tend to disguise the statistical properties of plaintext.

Remember strong passwords with this keyboard trick

keyboardEveryone knows that real people suck at coming up with strong passwords. They are either easy to remember and laughably weak, or decently strong and impossible
to recall. On top of that, it is highly recommended to use different passwords for different sites, so that compromising one won’t compromise the others. In this article, I follow Nobel laureate Manuel Blum’s recommendation of using not a password, but an easy to remember algorithm to come up with a way to generate strong, specific passwords for each site, and be able to remember them all.

In this talk, Manuel Blum asks four volunteers from the audience, who we presume not to have been prepared before the lecture, and explains to them a method which, when given a name to apply it to, leads them all to the same, apparently random result. The video does not reveal the method used, but some articles by Blum speak about mapping the alphabet (plus numbers) into a secret scrambled grid, and applying a secret walk to the successive letters of the name (presumably a website name) to be converted into something else. Thus, the user only needs to memorize the scrambled alphabet and the steps taken in the walk.

I don’t think I could do that, though, so here’s my counter-proposal: use the computer keyboard as my grid, and just memorize the method, plus maybe a simple code that I can change from time to time. Let’s say I want to come up with a strong password for amazon.com. I start, therefore, from the word “amazon”, which I am going to turn into something else. In order to increase security, I memorize the secret code “1234” (maybe I can’t memorize a scrambled alphabet, but this I can memorize). Now I do the following on an American qwerty keyboard like this:

keyboard

  1. Starting with the first letter in the original word, move down (and slightly to the right) on the keyboard as many keys as the first digit of the code. If this causes me to fall off the lower edge, I continue on the top row, on the key directly above the last one I touched. Since the first letter is “a” and the first digit is “1”, I move one key down from “a”, which is “z”.
  2. Repeat with the second letter of the name and the second digit, then do the same until all the letters have been transformed. If I run out of numbers, I take the first number again, and so on. Therefore the other letters are:
    1. “m” + 2 = “i” (wrap to “8” on the first step, and then down to “i”)
    2. “a” + 3 = “w” (wrap from “z” to “2” on the second step, and then down to “w”)
    3. “z” + 4 = “x” (wrap from “z” to “2” on the first step, and then down to “x”)
    4. “o” + 1 = “l” (observe that we go back to “1”, since we ran out of digits on the key)
    5. “n” + 2 = “u” (wrap from “n” to “7” on the first step, and then down to “u”)

Final result: “ziwxlu”, which likely does not appear in any dictionary and is therefore as hard to crack as a group of random letters. If the website demands that you add numbers, go ahead and add a few that you can easily remember (except “1234”, which would compromise the key). This time I will add “1111”, making the final password  “ziwxlu1111”. Never mind that the numerical part is weak; the strength is in the first part, which is one out of 366 = 2,176,782,336 possibilities (numbers are also part of the set).

What we have done is essentially to apply the Vigenère encryption algorithm to the word “amazon”, using “1234” as key and the qwerty keyboard read column by column as starting alphabet. Not secure by today’s standards, but again, we are using it to generate a password, which itself has a small probability of being revealed. Additionally, anyone having access to the password will still have to figure out the algorithm, since what I’ve presented above is just a sample. There are many other ways you can apply a key to a website name. For instance:

  • Do as above but instead moving up, or left, or right on the keyboard. Or maybe alternating directions, or even switching directions in a more complex pattern that is still easy to remember: a cross, a circle, etc.
  • Use an alphanumerical key, and then find the result key by doing a “Playfair” combination. In the classic Playfair cipher, two letters at a time combine into one, this way: if there are in the same row or column, take the letter following the first, right or down respectively, depending on whether they are on the same row (or is the same letter) or column. If they are on different row and column, trace a rectangle with the two letters as opposite corners, and then choose the upper new corner (or lower, or right, or left) as result. For instance: “”q” + “t” = “w” (same row), “r” + “v” = “f” (same column), “i” + “c” = “e” (neither). This method also can be subject to direction changes, if so desired.
  • Use no key at all, and just rely on direction changes to get the result. For instance, Blum used a one-step north-east-south-west repeating walk, which would turn “amazon” into “q,z/9m” on the qwerty keyboard, excluding non-character keys and the space bar.

There are several reasons why this method, even when not using a key at all, is easier and more secure than others.

  1. It is certainly easier than having to remember Blum’s secret square containing a scrambled alphabet. The keyboard is there, so why not use it? Otherwise, I might feel tempted to write down the square on a piece of paper because it is hard to do the translations all in the head. It is still hard to extract the key from a compromised password, since the details of the algorithm are unknown and the text sample very short.
  2. It is more secure than memorizing a single high-security password because, if that is compromised, then all logins are compromised. The result of the algorithm is very random-looking, which makes it hard to crack using a dictionary. Cracking by trying to guess the algorithm is hopeless, since you can use so many different possibilities for that too.
  3. Even if one password is compromised, that does not necessarily reveal the master key (“1234” in the above example) because the attacker does not know the exact series of steps in your algorithm. If he does, of course, he’ll get your key in no time at all, so don’t reveal your method. This is probably why Blum did not reveal his in the video.