Tweet
A little while back, here, we looked at splitting a password into two parts: A difficult, if not impossible, part to remember and written down and the other part memorable and committed to memory only.
I moved on a little and looked at obfuscating the memorable part before adding it to the written part. It then occurred to me that if the obfuscation was good enough we could dispense with writing anything down. By "good enough" I mean generating a ciphertext password from a memorable plaintext password that is indistinguishable from one generated at random.
With encryption/decryption we have Plaintext => Ciphertext => Plaintext. The Plaintext is secret. The Ciphertext is public as is the reversible method of encryption/decryption. We require that the Ciphertext is also secret and the method be irreversible.
We have an irreversible function built in PB: RND. With each iterate there is discarded truncation making it impossible to reverse engineer. To produce the same Ciphertext password for a given Plaintext password we have to use the same seed for RND but I did not want to have to remember a seed for a given Plaintext password. The obvious solution is to generate a seed from the Plaintext password.
One simple way to create such a seed is to calculate the CRC32 of the Plaintext password. Single precision is the preferred input for RANDOMIZE so the square root of the CRC32 is used. We have then:-
Seed = Sqr( CRC32( Plaintext password ) )
The Plaintext password is secret, so then is Seed.
Plaintext is often transposed as part of an encryption process. A key is used to allow reversibility. We don't use a key and use a random shuffle as the transposition.
In the following, Plaintext password means shuffled Plaintext password.
The next part of the method is an adaptation of Vigenére's substitution cipher. This cipher is 400 hundred years old and is obsolete and insecure in its original form.
Its simplest form is as follows
Each Plaintext character is read from the top row and the corresponding Ciphertext character is read from the row with a given left rotation/key in the first column. The '0' row is effectively a copy of the character set.
For example, DAY and keys 2, 24, 25 encrypts to FYX. Note that repetitions in the Plaintext are not reflected in the Ciphertext.
The keys used are secret to the sender and the recipient. We do not have a recipient and, as with Seed, we do not want to write anything down.
We depart from the classical approach by initially shuffling the copy character set and we also shuffle the rotation rows. For the keys, the first character of the Plaintext password uses the first rotation row, whatever that is after the rotation row shuffle. The second character of the Plaintext password uses the second rotation row, and so on.
The method can be described as follows:-
There is a security enhancement which is optional: A seed file. Here, we browse to a file, to be kept secret, and its contents are added to the Plaintext password for calculating Seed. In this case we have
Seed = Sqr( CRC32( Plaintext password || Seed file) )
The implementation of a Seed file introduces an interesting twist. For differing passwords instead of actually using different Plaintext passwords we could use the same Plaintext password but use different Seed files. In effect, the Seed file is simply a second password and we can choose to fix one and vary the other. We have also come full circle with the Plaintext password being the memorable part and the Seed file being effectively the part written down.
It is not thought that RND being only a 32 bit function, having then an entropy of 32 bits, is a weakness but to further frustrate an attack, if a Seed file is used RND is re-seeded using only the Seed file before the rotation rows are shuffled. This gives an entropy of 64 bits from 2^32 * 2^32.
EDIT: I was writing these notes during development. The above paragraph is no longer true. Re-seeding is now done with the shuffled Plaintext password. If a Seed file is used it is appended to both the Plaintext password and the shuffled Plaintext password. So, a Seed file is no longer a requirement to have the increased entropy.
Further edit: RND has been replaced by Mersenne Twister - see post #3. However, re-seeding is still done prior to shuffling the rotation rows.
There is a school of thought which recommends avoiding character repetition in passwords and another which does not.
One gauge to a password's strength is the NIST formula for randomly selected characters:-
Entropy = log2(n^k) where n = character set length and k is the password length. This can be written as k*log2(n).
The entropy of one character taken at random is then log2(n). In prohibiting that character from repetition the entropy of the next character taken at random is log2(n-1). In taking k characters the total entropy is:-
With n=94 and k=20 allowing repetitions gives 131.09 bits of entropy. Prohibiting repetition gives 127.95 bits. This is, roughly, a reduction of 3 bits. We would get the same reduction by dividing the character set by 8 (2^3), see below, or reducing the password length by about half a character. So, avoiding repetition reduces entropy.
In general, I favour allowing repetitions but the application here, called PWO.exe, has an option to prevent repetitions - the default being non-selection.
The power of password length over character set complexity is illustrated by considering a single character password and a multiple, m, of the character set length giving log2(n*m) = log2(n) + log2(m) which simplifies to log2(n) + 1 when m=2. So, doubling the complexity, for example, gives an increase of one bit per password character.
We get one bit of entropy per character for a character set of just two characters, 4.7 bits for 26 characters and 5.7 bits for 52 characters. In the latter case we can increase the total entropy by 5.7 bits just by adding one more character to the password.
Clearly, the total entropy is much more sensitive to password length than it is to character set complexity. So, even with a restrictive character set we could have a strong password provided it was sufficiently long. An alphanumeric set, for example, of 62 characters gives 5.95 bits per character. A strong password, exceeding 128 bits, can be got provided its length exceeded 21 characters ( chosen at random ); which, of course, may not be allowed in some cases.
Here is the form which is top down designed.
I have found that choosing the character set is easier done by selecting all of the subsets and then deselect those which cannot be used and then add additional characters in the custom character set text box, if any, that may be allowed.
If the custom character set is selected any entries cannot be repeated within its text box and nor can any entries repeat any available in any chosen subset above. 'Violations' are reported and the first, if more than one, character is highlighted.
The entries in the Plaintext password text box must, of course, only be those available in the chosen character set and offending entries are highlighted here too.
The Ciphertext box is unusual in that it does not obscure characters. This is a 'playing around' mode. In use the command switch '/secret' will see the Ciphertext text box removed. On clicking the Obfuscate button the Ciphertext password is placed onto the Clipboard for pasting to whatever requires the password. The Clipboard is reset on closing the application. If you have a Clipboard manager then a history will be kept and you may need to attend to that manually.
In 'playing around' mode I found that the application is better to be Topmost and in '/secret' mode it was found to be better not to be Topmost. Topmost is determined automatically.
The password text boxes use 10 point Courier to aid readability.
There is a status bar which details the password length, entropy (dependent upon allowing repetitions or not) and time taken; including reading a Seed file, if used. The entropy is calculated using the NIST formula assuming that my contention of the Ciphertext password being indistinguishable from one taken at random is true.
You may be very organised with your passwords and use something like TrueCrypt. However, how do you open TrueCrypt? TrueCrypt allows all of PWO's character subsets except the Alr Gr set (áéíóú) and passwords up to 64 characters long are allowed.
How about this 57 character password?
K=~jJYe6P(W)9*gzm_t"[email protected];|O~z`/MnbL^D0\nd_rS$1lK2u9o1Y$
With repetitions allowed the entropy is 374.5 bits. A brute force attack on the Ciphertext password will, on average, succeed at 2^(374.5/2) attempts. That is greater than 10^56. There is not a computer on the planet fast enough to get anyway near that and that may the case for some time to come.
The Plaintext password is:-
The time has come the walrus said to talk of many things.
There is an issue which I have not been able to resolve. '&' is available in the "`! ... .?" character set but it does not get displayed in a control's label. Obviously, this has something to do with hot-keys. How can I display '&'.
I moved on a little and looked at obfuscating the memorable part before adding it to the written part. It then occurred to me that if the obfuscation was good enough we could dispense with writing anything down. By "good enough" I mean generating a ciphertext password from a memorable plaintext password that is indistinguishable from one generated at random.
With encryption/decryption we have Plaintext => Ciphertext => Plaintext. The Plaintext is secret. The Ciphertext is public as is the reversible method of encryption/decryption. We require that the Ciphertext is also secret and the method be irreversible.
We have an irreversible function built in PB: RND. With each iterate there is discarded truncation making it impossible to reverse engineer. To produce the same Ciphertext password for a given Plaintext password we have to use the same seed for RND but I did not want to have to remember a seed for a given Plaintext password. The obvious solution is to generate a seed from the Plaintext password.
One simple way to create such a seed is to calculate the CRC32 of the Plaintext password. Single precision is the preferred input for RANDOMIZE so the square root of the CRC32 is used. We have then:-
Seed = Sqr( CRC32( Plaintext password ) )
The Plaintext password is secret, so then is Seed.
Plaintext is often transposed as part of an encryption process. A key is used to allow reversibility. We don't use a key and use a random shuffle as the transposition.
In the following, Plaintext password means shuffled Plaintext password.
The next part of the method is an adaptation of Vigenére's substitution cipher. This cipher is 400 hundred years old and is obsolete and insecure in its original form.
Its simplest form is as follows
Code:
A B C D E F G ...... X Y Z 0 A B C D E F G ...... X Y Z 1 B C D E F G H ...... Y Z A 2 C D E F G H I ...... Z A B ..... 24 Y Z A B C D E ...... V W X 25 Z A B C D E F ...... W X Y
For example, DAY and keys 2, 24, 25 encrypts to FYX. Note that repetitions in the Plaintext are not reflected in the Ciphertext.
The keys used are secret to the sender and the recipient. We do not have a recipient and, as with Seed, we do not want to write anything down.
We depart from the classical approach by initially shuffling the copy character set and we also shuffle the rotation rows. For the keys, the first character of the Plaintext password uses the first rotation row, whatever that is after the rotation row shuffle. The second character of the Plaintext password uses the second rotation row, and so on.
The method can be described as follows:-
Code:
Shuffle the Plaintext password.
Shuffle the copy character set.
Loop { Randomly rotate the copy character set.
Read a character.
}
Seed = Sqr( CRC32( Plaintext password || Seed file) )
The implementation of a Seed file introduces an interesting twist. For differing passwords instead of actually using different Plaintext passwords we could use the same Plaintext password but use different Seed files. In effect, the Seed file is simply a second password and we can choose to fix one and vary the other. We have also come full circle with the Plaintext password being the memorable part and the Seed file being effectively the part written down.
It is not thought that RND being only a 32 bit function, having then an entropy of 32 bits, is a weakness but to further frustrate an attack, if a Seed file is used RND is re-seeded using only the Seed file before the rotation rows are shuffled. This gives an entropy of 64 bits from 2^32 * 2^32.
EDIT: I was writing these notes during development. The above paragraph is no longer true. Re-seeding is now done with the shuffled Plaintext password. If a Seed file is used it is appended to both the Plaintext password and the shuffled Plaintext password. So, a Seed file is no longer a requirement to have the increased entropy.
Further edit: RND has been replaced by Mersenne Twister - see post #3. However, re-seeding is still done prior to shuffling the rotation rows.
There is a school of thought which recommends avoiding character repetition in passwords and another which does not.
One gauge to a password's strength is the NIST formula for randomly selected characters:-
Entropy = log2(n^k) where n = character set length and k is the password length. This can be written as k*log2(n).
The entropy of one character taken at random is then log2(n). In prohibiting that character from repetition the entropy of the next character taken at random is log2(n-1). In taking k characters the total entropy is:-
Code:
Entropy (No repetition) = log2(n) + log2(n-1) + ... + log2(n-(k-1))
= log2(n*(n-1)* ... *(n-(k-1))
= log2(n!/(n-k)!)
In general, I favour allowing repetitions but the application here, called PWO.exe, has an option to prevent repetitions - the default being non-selection.
The power of password length over character set complexity is illustrated by considering a single character password and a multiple, m, of the character set length giving log2(n*m) = log2(n) + log2(m) which simplifies to log2(n) + 1 when m=2. So, doubling the complexity, for example, gives an increase of one bit per password character.
We get one bit of entropy per character for a character set of just two characters, 4.7 bits for 26 characters and 5.7 bits for 52 characters. In the latter case we can increase the total entropy by 5.7 bits just by adding one more character to the password.
Clearly, the total entropy is much more sensitive to password length than it is to character set complexity. So, even with a restrictive character set we could have a strong password provided it was sufficiently long. An alphanumeric set, for example, of 62 characters gives 5.95 bits per character. A strong password, exceeding 128 bits, can be got provided its length exceeded 21 characters ( chosen at random ); which, of course, may not be allowed in some cases.
Here is the form which is top down designed.
I have found that choosing the character set is easier done by selecting all of the subsets and then deselect those which cannot be used and then add additional characters in the custom character set text box, if any, that may be allowed.
If the custom character set is selected any entries cannot be repeated within its text box and nor can any entries repeat any available in any chosen subset above. 'Violations' are reported and the first, if more than one, character is highlighted.
The entries in the Plaintext password text box must, of course, only be those available in the chosen character set and offending entries are highlighted here too.
The Ciphertext box is unusual in that it does not obscure characters. This is a 'playing around' mode. In use the command switch '/secret' will see the Ciphertext text box removed. On clicking the Obfuscate button the Ciphertext password is placed onto the Clipboard for pasting to whatever requires the password. The Clipboard is reset on closing the application. If you have a Clipboard manager then a history will be kept and you may need to attend to that manually.
In 'playing around' mode I found that the application is better to be Topmost and in '/secret' mode it was found to be better not to be Topmost. Topmost is determined automatically.
The password text boxes use 10 point Courier to aid readability.
There is a status bar which details the password length, entropy (dependent upon allowing repetitions or not) and time taken; including reading a Seed file, if used. The entropy is calculated using the NIST formula assuming that my contention of the Ciphertext password being indistinguishable from one taken at random is true.
You may be very organised with your passwords and use something like TrueCrypt. However, how do you open TrueCrypt? TrueCrypt allows all of PWO's character subsets except the Alr Gr set (áéíóú) and passwords up to 64 characters long are allowed.
How about this 57 character password?
K=~jJYe6P(W)9*gzm_t"[email protected];|O~z`/MnbL^D0\nd_rS$1lK2u9o1Y$
With repetitions allowed the entropy is 374.5 bits. A brute force attack on the Ciphertext password will, on average, succeed at 2^(374.5/2) attempts. That is greater than 10^56. There is not a computer on the planet fast enough to get anyway near that and that may the case for some time to come.
The Plaintext password is:-
The time has come the walrus said to talk of many things.
There is an issue which I have not been able to resolve. '&' is available in the "`! ... .?" character set but it does not get displayed in a control's label. Obviously, this has something to do with hot-keys. How can I display '&'.
Comment