Microblog: A very long article Wikipedia article on the orientation of toilet paper [Jun 7th, 22:52] [R]

Thursday, August 25th, 2011

Second Page

Translation: [ Google | Babelfish ]

Categories: [ Blog ]

Les résumés et les bières n'intéressent finalement pas grand monde, donc j'ai remplacé le filtre optionnel par une « seconde page » obligatoire. Pour désactiver ce filtre, il faut ajouter ?all=1 dans l'URL. Ceci s'applique aussi aux flux RSS.

Summaries and beers are not interesting to most people, so I replaced the optional filter with a mandatory “second page”. To disable this filter, add ?all=1 to the URL. The same applies to RSS feeds.

Yhteenvedot ja oluet eivät kiinnosta useimpia lukijoita, joten korvasin vapaaehtoisen suodattimen pakollisella “toisella sivulla”. Suodattimen voi pysäyttää lisäämällä ?all=1 URL-osoitteen loppuun. Sama koskee RSS-syötteitä.

[ Posted on August 25th, 2011 at 18:34 | no comment | ]

Tuesday, August 23rd, 2011

Dieharder Test

Categories: [ IT ]


It took about a week to generate a bit over 100 MB of random data with the arduino-based hardware random number generator. I used the JeeLink-based one, and the last chunk of random data (50 MB) was generated at a speed of 1562 bits/s.

And now for some statistical tests.

Fourmilab's ent test returns:

Entropy = 7.999998 bits per byte.
Optimum compression would reduce the size
of this 106315776 byte file by 0 percent.
Chi square distribution for 106315776 samples is 240.83, and randomly
would exceed this value 72.90 percent of the times.
Arithmetic mean value of data bytes is 127.4987 (127.5 = random).
Monte Carlo value for Pi is 3.140987091 (error 0.02 percent).
Serial correlation coefficient is 0.000165 (totally uncorrelated = 0.0).

I also ran the Dieharder test suite, which ran 40 tests on the data. Out of those, I got:

  • 34 PASSED
  • 1 POOR (1 RGB Bit Distribution Test out of 12 instances of the test)
  • 2 POSSIBLY WEAK (Diehard OPSO and Diehard Squeeze Test)
  • 3 FAILED (Diehard Sums Test and two instances of Marsaglia and Tsang GCD Test)

At the end of the series of tests, the software indicates that “The file file_input_raw was rewound 181 times”, meaning that I should get a lot more random data than 100 MB (ideally 18 GB, which means running the generator for 3.5 years) not to have the rewind the file for any of the tests.

The important question is however: 34 passed out of 40, is it good enough or not?

[ Posted on August 23rd, 2011 at 10:48 | 2 comments | ]

Thursday, August 18th, 2011

Journalisme du dimanche

Translation: [ Google | Babelfish ]

Categories: [ Grumbling | Science ]

Soit une dépèche AP Un Suédois essayait de fractionner des atomes dans sa cuisine (via fr.news.yahoo.com) commençant par (le gras a été rajouté)

« Un Suédois arrêté pour avoir tenté de réaliser une fission nucléaire dans sa cuisine »

Cette dépèche, reprise par Zignonet, devient Il essayait de construire un réacteur nucléaire dans sa cuisine (via fr.news.yahoo.com encore une fois) et commence par (le gras a été rajouté)

« Un Suédois de 31 ans a été arrêté fin juillet pour avoir fait une fission nucléaire à son domicile »

On n'a pas besoin d'un doctorat en physique nucléaire pour comprendre que tenter de réaliser et faire ne signifient pas la même chose. Il faut avoir appris à lire pour comprendre la différence, certes, c'est peut-être là que le bât blesse.

Un peu plus loin, AP indique

« il avait provoqué une petite fusion sur sa cuisinière »

que Zigonet interprète comme

« il avait réussi à provoquer une fission nucléaire dans sa cuisine »

Un élève de l'école primaire est capable de reconnaître que les mots fusion et fission ne sont pas les mêmes, même s'ils n'y a que deux lettres de différence entre les deux. Tout le monde conviendra que par exemple lapin et clampin, bien que n'ayant que deux lettres de différence, ne signifient pas la même chose : l'un est un adorable rongeur aux longues oreilles, tandis que l'autre non.

Les cours de physique atomique du lycée permettent de savoir que la seule fusion nucléaire obtenue sur Terre à ce jour concerne des atomes d'hydrogène, et que si l'apprenti Oppenheimer avait obtenu une fission nucléaire, la police n'aurait retrouvé personne à arrêter (mais les problèmes de surpopulation à Stockholm auraient été promptement résolus). Avec les histoires récentes de Fukushima, tout le monde devrait cependant savoir ce qu'est la fusion du combustible nucléaire (qui n'est pas la même chose que la fusion nucléaire), c'est à dire que ce dernier, produisant naturellement de la chaleur, peut fondre sous l'effet de cette dernière. On peut donc supposer que c'est ce qui s'est passé dans cette cuisine. AJOUT en lisant le blog du bonhomme je ne suis même pas sûr qu'il se soit agit de ça. Il a fait chauffer de l'americium, du radium et du beryllium dans de l'acide sulfurique et ça a explosé, probablement sous l'effet de l'ébullition de l'acide (qui bout à 337 °C, alors que les trois premiers fondent à 1176, 700 et 1287 °C respectivement).

En conclusion, quelques mots de différence changent complètement le sens d'un texte, et ce n'est pas parce qu'on publie des trucs sur le Web qu'on est un journaliste.

[ Posted on August 18th, 2011 at 17:41 | no comment | ]

A More Complicated PasswordCard!

Categories: [ IT ]


Angela Bartoli

To protect the password card from theft, there is one possibility. First, randomly generate and memorize a secret key composed of 12 numbers between 0 and 35 (one for each line of the card). Then for each letter of the mnemonic, shift this letter to the right (looping around the end of the line back to its beginning if needed) by the amount indicated by this line's secret key's digit before reading the symbol.

For an 8-symbol mnemonic, the entropy of this secret key is 41.4 bits, which gives a reasonnable amount of protection to the card even if it is stolen.

One obvious drawback is of course the strain it puts on the brain (although some may say it's good for the organ's health to work it out this way) and the time it takes to read one password. Another drawback is that the secret key is hard to remember, and if you forget it, you loose all your passwords.

Translating the secret key into letters and digits might make it easier to remember.

[ Posted on August 18th, 2011 at 17:24 | no comment | ]

Tuesday, August 16th, 2011

A Better PasswordCard?

Categories: [ IT ]


The PasswordCard sounds like a good idea (and it actually may be in practice), but I don't like it so much for three reasons:

  • The entropy is too low (64 bits spread over 232 symbols) and generated from an unknown source of entropy.
  • You have to memorize a cryptic symbol and a color for each password, which makes it easy to forget which symbol/color pair is associated with what password.
  • I didn't invent it :)

My current idea is to generate a similar card using a hardware random number generator so that each symbol on the card has an entropy of 6 bits (2592 bits in total on he card). I also would like to get rid of the method that consists in choosng one spot on the card and reading in one direction, and instead use the card as a lookup table for a substitution cipher: you choose a cleartext mnemonic for a given website with a length corresponding to the length of the password you want to generate (e.g., “EXAMPLEC” for an 8-symbol password to be used on example.com), and you generate the corresponding password by looking up the symbol corresponding to “E” on the first row of the card, then the one corresponding to “X” on the second row, “A” on the third, “M” on the fourth, and so on.

The drawbacks are numerous:

  • Reading a password this way is very slow and error-prone (the alternating gray and white areas and the repeated header lines make it only slightly less painful).
  • Generating two passwords from the same card is fine as long as the two mnemonics don't share the same characters in the same positions (e.g., “EXAMPLEC” and “EXNIHILO” share “EX” in positions 1 and 2) (if this is the case, the entropy of those particular symbols will be divided by the number of passwords sharing them).
  • The mnemonics are meant to be easy to remember, and therefore easy to guess by the thief of the card (that's howerver only slightly worse than the case of the stolen PasswordCard).
  • It requires a computer to generate a card that is readable in a small format, so the random bits are temporarily stored on a system that may be compromised (if the physical size of the card does not matter, you can generate such a card by rolling a pair of 6-sided dice about 729 times and writing the symbols down by hand).

There is one benefit though: the card looks very geeky :)

As usual, any comment/idea/criticism is welcome.

[ Posted on August 16th, 2011 at 23:14 | 1 comment | ]

Monday, August 15th, 2011

Hardware Random Number Generator

Categories: [ DIY/Arduino | IT ]


Software random number generators are usually so-called pseudo-random number generators, because they produce a deterministic sequence of numbers that have some of the properties of true random numbers. Obtaining genuinly random numbers howerver requires a non-deterministic processus as the source of randomness. Thermal noise in electronics or radioactive decay have been used, usually requiring an external device to be built and plugged to the computer.

Peter Knight's TrueRandom generates random bits by using the Arduino's ADC (with nothing connected to the analog input pin) to measure electronic noise. It flips the pin's internal pull-up resistor while the measure takes place to increase the amount of noise. The software then keeps only the least significant bit of the result, filters it using Von Neumann's whitening algorithm (read pairs of bits until they are of different values and return 0 (respectively 1) on a 01 (respectively 10) transition). There are several functions that generate different types of numbers based on those random bits.

I reused that code, modified it to allow using another pin than the Arduino's Analog0 and I made my own random number generator. I also wrote a Python script that reads the bits from the serial port, uses the SHA-1 hashing algorithm to distil the data (the raw data has about 6 bit of entropy per byte, distillation produces data with 7.999 bits of entropy per byte; based on the work of Jeff Connelly on IMOTP) and writes them to the standard output or into a file. On my Duemilanove, it can output about 1500 bits/s, while it outputs 1300 bits/s on a JeeLink. The latter makes it an easy-to-transport device that is reasonnably sturdy and fits in the pocket, even if its features (it contains a radio transceiver) are a bit overkill for the job (not to mention expensive).

I also adapted the core of the TrueRandom software to run on my ButtonBox (which is conveniently always connected to my desktop computer). There the output rate is a mere 300 bps, but it's still reasonnably fast for generating a few random numbers when needed (for example for generating one's own PasswordCard). The access to the ButtonBox is shared among multiple clients using button_box_server.py, so a modified Python script was used for obtaining the stream of random bits through the button_box_server.

I haven't had the patience to generate a few megabytes of random data to test the generator with the DieHarder test suite, but the output of Fourmilab's ent test tool looks reasonnable.

[ Posted on August 15th, 2011 at 11:08 | 2 comments | ]

Friday, August 12th, 2011

Password Management with the PasswordCard

Categories: [ IT ]

It all started a few days ago with this Xkcd strip. Someone pointed it out passwordcard.com to me, and it made me wonder how safe are the passwords generated with that tool. Those passwords are meant to be used on all those websites that require you to create a user account with a password. Using a single password for all those web sites means that when the attacker of one of those websites gets your password, he can access your account on every other website where you have an account.

Beware that I'm no mathematician, and neither am I a specialist in cryptography or information theory, but here are my thoughts on this system.

The generator is based on what looks like a 64-bit key, so in theory, the entropy is 64 bits, which is reasonnably much (it would take 6x108 years to break at 1000 attempts per second). However, since you need to feed the key to an unknown web server, the practical entropy is much less, since someone else than you knows the key. But let's assume you can generate the card yourself on a secure computer.

The symbols on the card are upper- and lower-case letters, and digits, which makes overall 62 possible combinations. This gives 5.95 bits of entropy per such symbol, if the symbol is randomly generated. Since the card is generated from 64 bits of entropy, you can take up to 10.7 symbols to generate one or more passwords without loosing any entropy. That is, a password made of one symbol will have 5.95 bits of entropy, a password made of two symbols will have twice that (11.9 bits), three symbols will be 17.9 bits and so on. If you take more than 10.7 symbols, the entropy of each symbol will be reduced, so that the entropy of the symbols in all your passwords altogether will never exceed 64 bits. For example, if you take 16 symbols to make 2 passwords of 8 symbols each, the entropy of each password will be 32 bits instead of the 47.6 bits of a single, 8-symbol password. A 32-bits-of-entropy password takes 50 days to break (at the example rate above) against about 7000 years for the 47.7-bit-of-entropy password.

Here are a few examples of password types and strengths:

  • 1 password of 6 symbols: 35.7 bits of entropy, cracked in 1.8 years
  • 1 password of 7 symbols: 41.7 bits of entropy, cracked in 112 years
  • 1 password of 8 symbols: 47.7 bits of entropy, cracked in 7000 years
  • 2 passwords of 6 symbols each: 32 bits of entropy, cracked in 50 days
  • 2 passwords of 7 symbols each: 32 bits of entropy, cracked in 50 days

However, if the card is stolen, the thief only has to test a few tens of thousands combinations to find a password made of 4-8 symbols (29 x 8 symbols, 8 reading directions and 5 possible password-lengths is 55680), which represent 15.8 bits of entropy and takes less than a minute to crack. Loosing the card is therefore a bad move.

As a conclusion, the password card is fine on the following three conditions:

  • Use a real random number for the key (e.g., by rolling 25 times a 6-sided die) or a hardware random number generator (there will be a post on that soon).
  • Use the card for passwords totalizing no more than 10 symbols (best to use only one password of 8, 9 or 10 symbols).
  • Do not lose your PasswordCard.

Disclaimer: once again, I'm no specialist in cryptography or information theory, but the above is based on how I understand those things. It may be completely wrong.

[ Posted on August 12th, 2011 at 21:52 | 2 comments | ]