WORK IN
PROGRESS
WORK IN
PROGRESS

Off The Grid
Options for Enhanced Security

In security system design, it's
impossible to be too paranoid.

No security system deserves to be trusted without a careful and critical examination of that system's potential vulnerabilities. For that reason, the Off The Grid security and attack analysis page examines the system's strength against various forms of active attack.

During the development and extensive discussions of the system, a number of possible enhancements were tossed around, examined, explored and considered. Although they do further strengthen the system in various ways, we concluded that on balance the simple base system, as described on the How to use the OTG system page, was already so strong that the additional strengthening didn't return enough to justify the additional difficulty.

However, since we did develop the extra strength approaches, it's worth sharing what we came up with in case they might be something you would like to consider. As we wrote above . . . it's impossible to be too paranoid.

Adding Non-Alphabetic Characters

gridborderTo the security aware password user, especially any user who is already familiar with GRC's other password-related work, including our Password Haystacks password strength evaluation system, the single biggest surprise might be that the standard Off The Grid system does not incorporate the generation of passwords containing non-alphabetic digits and other special characters.

During the development of OTG, we experimented with designs that did generate passwords having much larger character sets [see: 26x26 & 13x13]. But the trouble, aside from making the final grid much more noisy visually (and no way around that), was that there was then no way not to generate passwords without special characters. You got what you got. And that would be a problem any time a website refused to accept passwords containing special characters. A recent analysis of websites showed that a surprising percentage still refuse to allow complex passwords. So we needed another approach.

You may have noticed that the grid shown on the OTG introductory page contained an inner Latin Square region surrounded by a border of digits and special characters. As with the grid's inner composition, an important non-obvious property governs the design of that border: every row and column has a digit at one end and a special character at the other, and all of those border characters are randomly chosen and arranged, with the exception of the ten digits, the dash and dot at the center of the top border (which form the translation table). And even there, the rule of a digit and a special character at each end holds. Thus, as you are moving through the rows and columns of the grid, randomly chosen digits and special characters are continually available to you for whatever purpose you might wish.

There are no hard and fast rules for their use, but here are some example strategies for incorporating them into the resulting password:

  • Letting the grid CHOOSE:
    The password encoding scheme defines a current row or column and a direction of travel. This means that there is always a “border character” out at the end of the current row or column in the last direction of travel. So a potent scheme for embellishing OTG passwords with grid-chosen digits and non-digit special characters is to output the two characters following the target character as usual, then scan in the same direction to the end of that row or column out to the border and output whatever character is found there. This would generate passwords of the form <alpha><alpha><non-alpha> with three characters output for every domain name character input. Since eighteen characters might be longer than some sites allow, you might opt to reduce the OTG path lengths from six down to five or perhaps even four. This would result in passwords of fifteen or twelve characters respectively, but incorporating a great deal of entropy due to their inclusion of randomly chosen digits and non-digit special characters.

    (Remember that you can quickly and easily use our Password Haystacks page to quickly evaluate the attack resistance of any password format you are developing.)

  • Letting the grid HELP:
    As detailed above, letting the grid choose is terrific as long as the target website allows the use of non-digit special characters. The chances are 63 out of 64 (98.4%) that a password containing six randomly chosen digits and non-digits will contain at least one non-digit. Unfortunately, some sites that do allow digits don't also allow non-digit special characters. Since adding digits, when possible, is better than not adding anything at all, we can easily modify our “Let the grid choose” approach to “Let the grid help”: Since each row and column always contains one digit and one non-digit special character, we simply output the numerical digit out at the one of the ends of the current row or column. As before, the same comments about overall length and strength evaluation are relevant here.

  • Tack something onto the END:
    A third possibility that represents a useful compromise would be to simply tack on the final row's digit and non-digit special character, or perhaps just the final numerical digit. As the Password Haystacks page demonstrates, this significantly strengthens any alpha-only password while not increasing its length significantly. You could use the border character pointed to by final row traversal, or just always the digit that appears on that ending row.

Are special characters necessary?

Do we need more security?
To answer that (↑) question, let's look at the complexity of the character sequences generated by the standard OTG grid system: As we know, each domain name input character generates two password output characters. Using the “overshoot” method, neither of the output characters can be the same as the domain name character. So that means that the first output character could be any one of the remaining 25 alphabetic characters and the second output character could be any one of the remaining 24 characters. Since each could be either upper or lower case, this yields any one of 50 possibilities for the first and any of 48 possibilities for the second giving us a total of 2400 possible character pairs output for every character input.

Assuming that we use six characters from the domain name, that yields 2400 raised to the power of six (24006) possible combinations, which is exactly 191,102,976,000,000,000,000 possible twelve-character (six character-pair) passwords. (You can use our web based “Big Number Calculator” to confirm this for yourself if you wish.) If we assume that an online attacker is able to try 1,000 guesses per second, with 31,557,600 seconds per year, then 6,055,687,885 years would be required to try all possibilities. A million guesses per second reduces that to 6,055,688 years. And a billion guesses per second drops it all the way down to approximately 6,056 years.

Therefore, while it certainly is possible for us to increase the strength of the standard alphabet-only OTG system by adding non-alpha characters, the twelve random alphabetic characters produced by the standard use of the grid provides ample strength. And, if you stick with alpha-only, you don't ever need to worry about whether websites will accept more complex passwords.

Note that if a website requires the use of at least one digit, as some do, you could always simply add one somewhere. Even if you were to always do the same thing, even if your approach was known to an attacker, you would still have at least as much strength as you do without using any digits . . . which we have already seen is more than sufficient.

If you wanted more security WITH full compatibility...
You could also have that easily by simply encoding more of a domain name's characters. Even the very short domain name “GRC.COM” consists of seven characters which could be encoded, and most domain names are longer. So there are usually plenty of domain name characters to encode. As we have seen, each additional character-pair added increases the attack strength by 2400 times. So simply using seven domain name input characters to produce 14 alphabetic-only output characters yields 24007 = 458,647,142,400,000,000,000,000 possible combinations, which would require 14,533,651 years to test at one billion attempts per second.

Thus, the simplest and most universally compatible means of increasing the system's security is to make your passwords longer. (Though we think that 12 output characters is already very good security!) But if you do want to embellish your passwords with non-alphabetic characters, the Off The Grid system makes that possible too.

Further obscuring an individual grid's structural details

The Off The Grid security and attack analysis page examines the OTG system from the perspective of an attacker who might somehow obtain one or more (or many) secret domain name and OTG password pairs of a given user. On that page we attempt to determine to what degree the system's security could be compromised in such a way that additional passwords might be determined for other domain names. In other words, how much of a grid's secret structure is revealed by an attacker knowing the specific passwords generated by specific domain names? Please see that page for the details of that analysis. However, as you probably expect, this entire OTG system would never have been disclosed and published if the system hadn't survived that analysis with plenty of margin to spare. (It did!) In fact, so little useful information about the structure of any individual user's OTG grid is leaked when existing domain names and their associated passwords are discovered that everyone who participated in that analysis is comfortable with using the system as it is, without additional enhancement(s).

But you may also know by now that I always want to explore all possible avenues for improvement . . . because you never know what you might find until you look.

So here's the theoretical structural leakage concern: An attacker who obtains one or more matching domain name and password pairs generated by an OTG grid obtains multiple three-character “triples” of character sequences occurring in the user's grid. The attacker knows the first character of each triple, since it comes directly from the domain name. And the attacker knows the two characters that lie directly adjacent to it on the grid, since those are the two characters of the output. By assembling each character of the domain name with each character pair of the associated password, the attacker can generate a set of “triples” which are known to occur somewhere within the user's grid. As you can see, this reveals pieces of the composition of a user's OTG grid. As mentioned above, the security and attack analysis page examines what an attacker might be able to do with one or more sets of these triples, i.e. is this a problem?

However, here we will examine a means of hiding even that (small and unusable) amount of our grid's composition.

We've already seen that every OTG grid has a Latin Square in its center, surrounded by a border of carefully designed special characters such that every row and column always contains one of each. Every OTG grid has one additional non-obvious property: In any direction of travel, up, down, left or right, including wrapping around an edge, continuous runs of the same capitalization are limited to three characters. If you look back at the grid on the introduction page you'll see that nowhere, in any direction, are there ever more than three characters together all with the same case. The capitalization is still locally random and unpredictable, but it also has this significant property.

Okay . . . so??
This special property makes it practical to enhance the “overshoot” method of finding our output character pair: After encountering the target character we are scanning to, instead of taking the next two characters adjacent to it while travelling in the same direction, we hold off until we have first encountered one of each alphabetic case of intervening characters.

casemap

In the example above, we were scanning to the right for the next domain name character “o”, which we found. Then, instead of outputting the two characters “xl” that follow, we continue scanning until we have encountered at least one lowercase character and at least one uppercase. In this example, the first “x” we encounter satisfies our search for a lowercase character, and the uppercase “J” satisfies our search for the first uppercase character. With both searches satisfied, we then output the next pair of characters encountered, which is “FZ”.

The power of this approach is that it “repurposes” the grid's variable capitalization in a way that cannot be known to an attacker. Since we wait for at least one of each case before outputting, and since continuous runs of the same case are limited to three characters, the two characters that are eventually outputted are always spaced between two and six characters away from the domain name target character. And since we don't output the characters we are skipping over, their case information is not contained in our output and attackers can never know what the spacing was. The three letter “triples” are thus broken up so that the attacker no longer gets this information.

It's true that this scheme still reveals pairs of characters that are adjacent since successive output characters are adjacent. If we wished to eliminate even that, we could output only one character after encountering both cases, then output the second character only after again encountering both cases. This would completely break up the “triples” with an unknowable number (2 to 6) of separating characters.

But once again, as the security and attack analysis page demonstrates, none of these additional enhancement measures are necessary for the Off The Grid system to deliver extremely good security. They were presented here for completeness, because they were developed and considered during the development of the OTG system and ultimately proved to be unnecessary. The simpler the system is to use, for more it will be used. The creation of a usable system was our goal.

Off The Grid Resource Pages:

Jump to top of page
Gibson Research Corporation is owned and operated by Steve Gibson.  The contents
of this page are Copyright (c) 2016 Gibson Research Corporation. SpinRite, ShieldsUP,
NanoProbe, and any other indicated trademarks are registered trademarks of Gibson
Research Corporation, Laguna Hills, CA, USA. GRC's web and customer privacy policy.
Jump to top of page

Last Edit: Aug 21, 2011 at 09:40 (2,253.43 days ago)Viewed 3 times per day