Announcing Rock Salt™

Rock Salt™ is a method for storing and accessing password verification data on multi-user computer systems that resists remote attacks. Along with commonly-employed measures that limit the number of unsuccessful attempts to login or otherwise verify a password, it allows users to choose relatively simple passwords with full security. The secret component cannot be easily leaked or exfiltrated by malware, does not require periodic backup and is isolated in a way that allows it to be protected by conventional security measures, such as safes, alarm systems and video surveillance, from attackers who somehow gain access to the computing facility.

I announced Rock Salt on Tuesday, August 2, 2016 at the Passwords16 conference in Las Vegas. My presentation slides are now available at https://www.researchgate.net/publication/305849439_Rock_Salt_A_Method_for_Securely_Storing_and_Utilizing_Password_Validation_Data

Video of the presentation should be available soon at passwordscon.org.

My Thoughts on Strong Encryption

The White House recently asked the public to “Share Your Thoughts on Strong Encryption”  Here is the link to the White House comment form. And here is what I wrote:

Response to the White House request to 

“Share Your Thoughts on Strong Encryption"

Comments by 

Arnold G. Reinhold

December 13, 2015

In September 1999, I wrote a briefing paper for the Cato Institute titled “Strong Cryptography The Global Tide of Change.” It’s available on-line at: 

  http://object.cato.org/sites/cato.org/files/pubs/pdf/bp51.pdf 

Back then the Clinton administration wanted encryption systems to include a feature allowing government access to encrypted data, just as the FBI wishes today. Sixteen years ago I wrote:

“Cryptographic technology is so widespread that it is impossible to stop. If any major governments, terrorist organizations, or drug cartels are not now using strong cryptography, it is not because of lack of availability or lack of reliable suppliers. There are many firms overseas that are willing to provide cryptographic software, and, for better or for worse, some of the cryptographic products most widely available on the international market were originally made in the United States.“

Concerning the risks of encryption backdoors, I wrote:

“…key recovery will create new targets for miscreants to attack. Given the enormous value that the data in key repositories represents, it is only a matter of time before they will be compromised. Even the best security arrangements are vulnerable to bribes, blackmail, and threats of bodily harm. Over time, commitment to security will wither under cost pressures and boredom.“

We saw an example of the latter point this year at the Office of Personnel Management when the security clearance forms and data of millions of cleared workers, including all our intelligence agents, were electronically stolen by China.

Tools for surveillance have multiplied since 1999

Since my briefing paper appeared, there have been many changes in technology and legislation that have enhanced the ability of law enforcement and the intelligence community to track terrorists and gather evidence:

o The dramatic drop in the cost of mass storage (by a factor of over 300) has allowed the indefinite retention of almost every detail of each American’s lives. Lower storage and processing costs have enabled the big data movement, which stores and analyzes every financial transaction we make as well as all our interactions with the Internet. As business records, such data is available to the government without search warrants.

o The Patriot Act was passed giving the FBI broader power to demand data through secret National Security Letters, hundreds of thousands of which have been issued. The act was also interpreted by the Bush administration to allow wholesale collection of metadata on every U.S. citizens’ telephone and electronic communications, creating a database that reveals each person and organization with whom we communicate. While recent legislation has moved this database from government data centers to those of the private telecommunication carriers, it is still available for government search.

o The growth of cell phone usage to near ubiquity has, as a by product, allowed the movements of every individual who carries one to be tracked at all times. Newer phones with built-in GPS must, by law, allow tracking to the nearest 50 meters for most calls. While this data is only needed temporarily to route calls and pass on location data to emergency responders, it is being stored indefinitely. Again, as business records, this data is available to the government without search warrants.

o License plate readers have become cheap and reliable, and are being used on traffic signals and roving police patrol cars, providing another means to track our movements. 

o Surveillance video cameras have become common and are being linked in many jurisdictions. Combined with rapidly improving face recognition software, they provide yet a third way to track individuals, even those who avoid cell phones and private automobiles. 

o The rise in social media has placed a vast array of information about individuals on line. Accounts associated with terrorist organizations designed to recruit new terrorists can and no doubt do provide a wealth of intelligence about potential threats.

o We now know that the NSA has actively worked to weaken security standards intended to protect electronic communication systems, many of which are essential to civil safety. 

o We also learned that the NSA has developed an extensive catalog of technologies that can infiltrate computer network systems and circumvent their encryption.

These new technologies have greatly expanded the arsenal of our law enforcement and intelligence agencies, but they also threaten to entrench despotic regimes around the world by creating a totalitarian infrastructure far beyond what George Orwell imagined in 1984. Use of strong encryption to protect our personal records and communications from government snooping is one of the last lines of defense for individuals here and abroad who wish to resist oppressive governments. 

We need stronger security systems, not weaker

Since 1999, the dangers of weak electronic security have become all too clear.

o The have been a long series of massive data breaches affecting even companies in the security industry. Tens of millions of U.S. citizens have been affected.

o Cyber criminals have developed “ransomware” systems so effective that the FBI’s best advice to victims is to pay the ransom. Even police departments have paid.

o Current government officials have warned of the dangers of cyber attack from China, Russia, North Korea, Iran, and even ISIL.

o In particular there is evidence that computers that control critical infrastructure, such as our water supplies and the electric power grid have already been infiltrated by malware controlled by foreign actors.

Weakening the security of our electronic networks is the last thing we should be considering in light of these threats.

We don’t want the terrorists to go silent

The recent attacks in Paris and San Bernardino demonstrate that small, self-sufficient terror cells need not communicate electronically in ways that would reveal their intentions. It does not take much imagination to see how others can do this in the future. U.S. government action to require backdoors in encryption products would only alert terrorists to shun any electronic communication whatsoever in planning their operations. Even if backdoored encryption exposes a few terrorist plots, others intent on evil will soon learn the lesson. But a great deal of valuable information can be gleaned from patterns of electronic communication, even if the messages themselves cannot be read. Requiring backdoors could shut off this valuable intelligence and truly blind us.

Please don’t weaken our security

Weakening the encryption on the computers we use has damaged and will continue to damage the security of our infrastructure, but it won’t stop the terrorists. As I wrote in 1999: 

“… the simple reality that strong encryption is widely available around the globe can rescue us from endless debate.”

Respectfully submitted,

Arnold G. Reinhold

It's Back to the Future day!

Tomorrow, October 21, 2015, is Back to the Future day. It's the date when the characters in the 1985 movie Back to the Future, Part !!, arrive in the future, 30 years ahead. 

In the first movie in the trilogy, Back to the Future, Part I, Doc Emit Brown accidentally sends Marty McFly 30 years back to 1955 carrying a 1985 Camcorder. Unable to use the broken time machine DeLorean to get back to ’85, Mary looks up the younger 1955 Doc Brown who marvels at the Camcorder, calling it “astounding, a television studio in a box.’ and is able to hook it up to his 1955 black and white TV. Was that realistic?

The transistor was invented in 1948, and the possibility of integrated circuits was being discussed in the early 1950s. In 1955 TV studios were recording programs on movie film using Kinescope technology. Ampex Corporation sold the first commercial video tape recorder, the $50,000 VR-1000, in 1956, but it is quite possible a know-everything inventor like Doc was already aware of the technology being developed.  The video output from the 1985 Camcorder would have been a clearly marked RCA connector. Those connectors date back to the 1940s, when RCA introduced them to allow record players to be connected to radio consoles. 

Attaching an oscilloscope to the connecter, Brown would quickly recognize a baseband television signal. It would be in “compatible color” NTSC, but that standard came out in 1953. Television receivers of the time did not generally have a video input, but adding one to a vacuum tube receiver would not be hard at all, a capacitor to the grid of the video amplifier stage would do it. And since NTCS color was designed to be compatible with older black and white sets, it all should just work.

Presumably Mary’s camcorder batteries were not completely discharged and it would be simple for Doc Brown to measure their voltage (if it wasn’t clearly marked on the unit) and hook up a suitable low-voltage DC power supply, or even a battery.

So yes, that scene in the film was realistic.

Now suppose the movie was remade 30 years later in 2015, the arrival year in Back the the Future, Part II. Marty would presumably be carrying an iPhone 6s. What would a 1955 Doc brown have made of that? 

Connecting the iPhone to his 1955 TV seems unlikely. The iPhone does not output an NTSC analog TV signal. The video signal it does output was unknown in 1955 and likely too fast for Doc’s oscilloscope to decode. While composite video adaptors are available, there is no reason Marty would have one with him. But of course Doc Brown could have watched the video on the iPhone itself.

Power is a bigger problem. If Marty happened to have a standard USB AC adaptor and Apple Lightning cable, it would plug into a 1955 ungrounded wall outlet, without any adapter. If not, Doc would likely be stumped. The Lightning plug has a chip inside that authenticates itself to the iPhone to prevent cables unauthorized by Apple from working, so there would be no way for Doc to connect external power through that port. The best he could do would be to carefully open the iPhone case, tricky to do without damaging the delicate insides, and charge the battery directly. 

In short, while a 1985 Camcorder would be comprehensible to a 1955 inventor, a 2015 iPhone would be darn close to magic. What will 2045 bring? Will vintage movie buffs be able to understand Back to the Future without interpretive notes?

The lesson for computer security: It's hard to predict the future of technology. Long term security requires very conservative designs. 

Time to add a word

Time to add a word

For the average user I now recommend a passphrase with six Diceware words, or five words with one extra character chosen and placed at random. 

This is a change from my previous advice. Since Diceware was created in 1995, I have recommended five words as a suitable passphrase length for an average user.  For people with more stringent requirements and where the passphrase was being used directly to form a cryptographic key, I have suggested 6 words or more.

I had previously written that longer Diceware passphrases might be vulnerable by about 2014. Well it's 2014. Today criminal gangs probably have access to more computing power then the NSA did when this page first appeared. So I am upping my passphrase length advice by one word.

To understand why, here is an article about a password cracking machine built using 25 AMD Radeon graphics cards. It can test 350 billion possible password per second using Microsoft Windows’ NTLM password algorithm. They claim they can crack a random 8-character password in under six hours. At that speed, attacking a 5-word Diceware passphrase would take on average of 7,300 hours or 10 months to find the correct passphrase, assuming they knew you were using Diceware and developed equally efficient software designed to try only valid Diceware words. And NTLM is one of the easier password hashing algorithms to attack.

Criminal gangs have built botnets from thousands of computers infected with their malware. Marshaling large numbers of these computers they control might allow them to crack a five word passphrase in a reasonable amount of time. But tying up thousands of computers is probably more effort than criminals would want to expend on an average person’s data. They have many potential victims with weaker passwords that take much less work to exploit.

Still computer power keeps increasing, especially in advanced graphics processors, which are easily adapted to cracking work. Five words would still be enough for most uses if software designers used good key stretching, but too many do not and it is hard to know for sure which do. So I felt it was time to recommend that longer passphrases start being used. If you are using a 5 word passphrase, consider adding a random character as I suggest at diceware.com. It will make your passphrase about a thousand time more difficult to crack. Adding a sixth word makes it 7776 times harder. Take your pick, and read the Diceware.com FAQ for more information.

Making Random Letter Passwords Memorable

Making Random Letter Passwords Memorable

Arnold G. Reinhold

Cambridge, Massachusetts, USA

August 28, 2011

Abstract

A method is presented that accepts a random string of up to 10 letters and uses a look-up table to produce a mnemonic English sentence having those letters as the initial letter of each word. This method offers more predictable security than asking users who wish to create a strong password to think of a sentence and use the initials of each word in that sentence as the password.

Introduction

As personal computers become more powerful, attacks on password management systems are becoming difficult to prevent. Many authentication systems protect passwords by only storing a cryptographic hash of each password. However, if an attacker gains access to stored password hashes, they can attempt to crack the hashes using dictionaries of common passwords or brute force searches of all character combinations. The availability of high performance general-purpose graphics processors (GPGPUs) that can be programmed to carry out hash attacks exacerbates the problem. (Davis 2011) Cybercriminals have assembled large networks of computers they control (botnets) and can use CPUs and GPUs on the compromised machines to attack password hashes they have collected. Passwords used to generate cryptographic keys, such as those used for disk encryption or to protect wireless networks, have similar vulnerabilities.

In response to these threats, users are often encouraged (or coerced) to employ stronger passwords. Common ways of doing this include requiring a minimum length and a mix of upper and lower case letters, number and special characters. The latter approach can have mixed results. Users often follow predictable strategies to meet those requirements, modifying their passwords in minimal ways that have only modest impact on an attacker’s search difficulty.

Another common strategy suggests users think of a phrase that is memorable and use the initial letters of each word in that phrase to form their password, perhaps substituting words or letters with numbers or symbols, 2Bor~2B? for example .However this approach depends on the user being sufficiently clever and creative.  Many users will choose common phrases, such as lyrics from popular songs, and use predictable letter and word substitutions, such as “$” for “S”, “1” for “L” and “3” for “E”. Also the distribution of initial letters of words in English and other natural languages is far from uniform, giving attackers an additional advantage.

A more rigorously secure method is to offer users a password made up of characters chosen completely at random. Selecting uniformly distributed random characters offers the maximum possible entropy for a given password length and character set. However, this approach is not widely employed because of concerns that users find such passwords too difficult to remember.

The sentence generator approach

This paper proposes a different approach that offers the best features of the last two methods. A fully random password is created first and that password is then used to generate a mnemonic sentence – one where the initial letters of each word form the password. Since the random password is generated first, the selected sentence cannot diminish security, as long as it is kept secret. 

The sentence is generated from the password using s look up table, Table 1, which consists of 10 columns and 26 rows. Every column has 26 English words in alphabetical order, each starting with a different letter of the alphabet (a-z). The one exception is the “x” row where words starting with “ex” are used. Each column contains one grammatical form. The columns are arranged to produce a proper English sentence regardless of which row each word comes from. The column pattern from left to right is: proper name, adjective, noun, adverb, verb, adjective, noun, gerund, adjective, noun.

Give any string of 10 letters from the English alphabet, Table 1 can generate an English sentence consisting of ten words whose initials are those letters (with words that start with “ex” standing for “x”). Thus any random password of 10 letters produces a unique mnemonic sentence for that password. For example the password vmyhvxklke generates the sentence:

Vivian's merry yankees hopelessly view excellent kings leaving keen energy.

While not all sentences generated in this way are immediately meaningful, they can be easier to remember than the password itself. Simple techniques, such as visualizing the scene suggested by the sentence, can further aid memorization.

Table 1. Sentence generating matrix

‑‑	Name	adj	noun	adv	verb	adj	noun	gerund	adj	noun
	1	2	3	4	5	6	7	8	9	10
A	Arnold's	amazing	artists	always	arrest	angry	ants	arousing	awful	admiration
B	Bob's	big	brothers	boldly	batter	bossy	boys	bringing	boastful	bliss
C	Charlie's	cuddly	cats	craftily	cover	crazy	crooks	causing	cold	comfort
D	Dona's	deadly	ducks	deftly	drop	dumb	doctors	defying	dumb	delight
E	Ed's	empty	editors	easily	engage	eager	eels	enjoying	easy	energy
F	Frank's	fine	frogs	foolishly	fight	fat	foxes	finding	fast	fame
G	Gloria's	golden	goats	gaily	grab	green	goons	gaining	glorious	growth
H	Hana's	hot	hippos	hopelessly	hold	heavy	horses	helping	happy	health
I	Ivy's	interesting	infants	intensely	inject	incompetent	idiots	insulting	intense	interest
J	Jane's	jolly	judges	joyously	join	jealous	jokers	joining	juvenile	joy
K	Ken's	kissable	kittens	kindly	keep	kinky	kings	killing	keen	karma
L	Lucy's	lonely	llamas	laughingly	lash	lowly	librarians	leaving	lurid	love
M	Mary's	merry	mermaids	morosely	mangle	mad	monsters	making	messy	music
N	Nancy's	nice	nuns	noisily	nab	naughty	nerds	noting	neglected	nothingness
O	Olga's	old	owls	often	ogle	oily	orcs	owning	open	obsession
P	Pete's	pink	peacocks	playfully	pester	poor	pigs	packing	proud	power
Q	Quincy's	quiet	quails	quickly	query	quaking	queens	questioning	queer	quality
R	Randy's	red	rodents	regretfully	ruin	rude	robbers	rejecting	redolent	refreshment
S	Sue's	smooth	snails	swiftly	slay	snarky	slugs	seeking	simple	success
T	Tom's	tiny	tigers	timidly	tackle	tired	thugs	testing	tenuous	truth
U	Uri's	urban	umpires	urgently	upset	ugly	uncles	urging	useless	unity
V	Vivian's	vivacious	vampires	vividly	view	vicious	vandals	viewing	velvet	victory
W	Walt's	wild	wolves	willingly	wrestle	wimpy	wardens	wishing	witty	wisdom
X	Xavier's	eXotic	eXecutives	eXcitedly	eXpel	eXcellent	eXperts	eXtracting	eXtreme	eXcess
Y	Yolanda's	yelping	yankees	yearningly	yank	yellow	youths	yielding	yummy	yogurt
Z	Zed's	zigzagging	zebras	zealously	zone	zany	zombies	zooming	zesty	zeros

Strength of all-letter passwords

A 10 letter random password has 10 x log₂ (26) = 47.0 bits of entropy. For higher security, two sentences can be generated. If both are 10 letters long, the resulting password will have 94 bits of entropy, well exceeding NIST 800-63 guidelines for cryptographic strength (80 bits).

The table can be easily adapted to generate shorter sentences. Thus a 9 letter password would simply omit column 9, Vivian's merry yankees hopelessly view excellent kings leaving energy. An 8 letter password could omit columns 8 and 9 while making the word from column 8 possessive: Vivian's merry yankees hopelessly view excellent kings’ energy. For 7 letters, omit the last three columns, and so on.

Thus a 17 letter password, offering 80 bit security, could be represented by a 10 word sentence and a 7 word sentence, or a 9 and an 8 word sentence.

Random passwords consisting of only English letters have less entropy per character than random passwords selected from a larger character set, but additional letters can be added to make up the difference.  For example, a random 10 English letter password has a bit more entropy than a 7 character random password selected from all printable 7-bit ASCII characters (95 possibilities), which has 45.9 bits of entropy. To match the 65.7 bit entropy of a 10 character all-printable-ASCII password such as U{l>gPzH:Z requires an English letter password with 14 letters, which is longer, but arguably more memorable, at least when used with the method proposed here. Note that on many mobile devices, such as the Apple iPhone, it is more difficult to type a password randomly selected from all printable ASCII characters because multiple shifts are needed to access different groups of characters.

Other security impacts

The sentence generating approach table has few security limitations. Of course, the sentence generated must be afforded the same level of security protection as the password itself. And asking users to submit their password over the Internet to get their sentence has obvious security risks. It is better to display the sentence at the same time the password is generated or perform the table lookup locally.

The choice of words has no security implication as long as there is one word for each letter in the alphabet in every column. The words in Table 1 were selected to maximize the likelihood of a somewhat meaningful sentence, while minimizing the likelihood of a sentence with sexually suggestive or scatological meaning. While some might find an X-rated sentence easier to remember, others might find such sentences offensive and organizations might be reluctant to employ such tables to avoid creating a hostile work environment.

Tables for other languages and alphabets are feasible. Different tables could be created for variety, particularly when more than one sentence is needed to meet strength objectives. Other possibilities for password mnemonics include random poems, songs, haiku, limericks and similar short literary works.

Implementation

A 10 letter random password can be selected uniformly from the English alphabet using a strong random number generator, such as CryptGenRandom on Microsoft Windows systems, and /dev/random on Unix, Linux or MacOS X systems. The Python programming language has a SystemRandom class that uses either CryptGenRandom or /dev/random, depending on the operating system on which it is running.

An ideal implementation would be to offer a user a randomly generated password and a mnemonic sentence when a new account is created or a password is to be changed on an existing account.

Users wishing to use this system needn’t wait until it is adopted by password management systems. Strong random passwords can be generated manually using dice, playing cards or letter tiles. (Reinhold 2000)

If numbers, upper case letters and special characters are needed to meet password composition policy, they can be added easily. Nouns can be capitalized and normal sentence punctuation added. Such steps add security only if an attacker is unaware of the method used, however they never diminish security. Net additional security can be achieved by prefixing the first and second adjectives with a random number, in which case 3.3 bits of entropy are added per digit. Such a sentence would still be meaningful to a user, for example, Vivian's 23 merry yankees hopelessly view 7 excellent kings leaving keen energy would yield the password v23myhv7xklke.

Conclusion

The difficulty of getting users to employ strong passwords is a major challenge to cyber security. The method presented here can help in that effort by giving users an easier way to remember a random password.

References

Davis 2011, Joshua Davis and Richard Boyd, Teraflop Troubles: The Power of Graphics Processing Units May Threaten the World’s Password Security System, Georgia Tech Research Institute Case Study, 2011

Reinhold 2000, Arnold Reinhold, Picking a strong Passphrase using Diceware, Internet Secrets, 2nd Edition, John R. Levine, Editor, Chapter 37, p. 831 IDG Books, 2000, ISBN 0-7645-3239-1, also www.diceware.com.

Copyright notice:

Copyright © 2011 by Arnold G. Reinhold. This paper, including Table 1, is hereby released by the author under the terms of the Creative Commons 3.0 with Attribution License (CC-BY).