https
WORK IN
PROGRESS
WORK IN
PROGRESS

Off The Grid
Security and Attack Analysis
This page is currently incomplete.

It will soon contain an analysis of the nature of the information that the OTG system “leaks” due to the fact that its passwords are formed from bits and pieces of the user's grid. This is already discussed at some length in the second answer on the OTG Frequently Asked Questions page. Please see that if you are interested in the security of the OTG system.)

Essentially, every OTG password inherently contains some structural information about the grid. But this page will show that so much remains uncertain and unknowable that even if an attacker were to obtain a great many samples of a user's domain names and matching OTG passwords, they would still be unable to reassemble the user's grid.

(Notes to myself) Discussion Points:

Reader Beware: Much of what's below refers to an earlier design of the OTG system [see: 26x26 & 13x13], so please do not rely upon any of this information until the page is complete.

How many steps should you take?
If you were using the PPC system to encipher a very long domain name such as “allthingsconsidered.com” the task of following that name's entire path to the end would quickly become quite tedious and prone to error. It is also unnecessary for the security of the Personal Paper Cipher.

As we'll see next, the system's Phase 2 (enciphering) begins at the location determined by the initial Phase 1 path following.

The first question that arises is:  How secure is this?

As we will see below, only a portion of the Personal Paper Cipher's security comes from the attacker's ignorance of the configuration of the Latin Square we are using. But it does raise the question: could an attacker guess or computationally “brute force” the configuration of the particular Square we are using?

lsnThe Cipher's design actively prevents the disclosure of any particular Square, so the feasibility of guessing or brute forcing a Square's configuration, assuming the absence of any other clues, is primarily determined by the total number of possible Latin Squares from among which ours was chosen. As was mentioned in the “Latin Squares” box above, mathematicians who have studied Latin Squares have only been able to obtain an exact count for Squares having sizes up to 11x11 (and the exact count for 11x11 Squares was only recently obtained.) What the math gurus have been able to state with certainty, is that the lower bound on the number of Latin Squares, of a given size 'n' by 'n' is given by the equation shown on the left. In other words, although no one knows exactly how many specific Latin Square configurations there are of any size larger than 11x11 (because there are too many!), we do know that there are at least as many as specified by that equation. But how many is that?

lsn2Plugging the number (n=26) into the lower bound equation for the Personal Paper Cipher's 26x26 Latin Square results in a number so large as to be rather ridiculous. It is: 9 336 974 347 720 076 203 095 381 302 683 075 484 706 012 030 875 383 265 106 777 232 515 384 291 786 329 470 875 840 456 766 821 029 030 235 438 914 174 291 844 167 774 650 650 291 329 460 401 751 489 013 555 810 781 700 163 431 985 765 122 298 613 958 200 230 192 236 631 943 316 085 768 502 914 719 815 963 609 471 283 139 690 899 669 496 766 419 404 467 151 772 248 428 431 825 394 305 641 480 706 711 487 437 686 906 450 684 680 968 293 622 304 401 609 062 321 217 193 606 241 756 724 745 170 796 786 016 394 203 303 300 168 583 550 145 590 123 023 289 449 057 087

This number, expressed in scientific notation, is: 9.337 x 10426 and the log(2) (logarithm base 2) is approximately 1418. This means that a binary number having at least 1418 bits (because this is the known lower bound) would be required to specify one of the 26x26 Latin Squares possible.

During the development of this Personal Paper Cipher system, we developed several different algorithms that randomly found one single Latin Square from among all of those that are possible. However, to assure TNO (trust no one) style privacy, this code must run as JavaScript on the user's own web browser (that way no one, not even GRC, has any idea what your individual Cipher Square looks like). The solutions we developed did allow for highly efficient client-side JavaScript implementation, but sometimes the search took so long that browser warning messages popped up, and some users have older and much slower systems. In the end we chose a secure compromise that allows us to quickly choose one Latin Square from among a smaller, but still massive subset of all possible Squares.

The final algorithm for Latin Square generation used by the PPC system randomly selects one Latin Square from among a subset containing 26!2 x 25! x 6 Squares. This is 15 136 831 721 341 031 145 555 109 377 300 868 031 260 208 035 408 929 173 274 624 000 000 000 000 000 000; in scientific notation: 1.513 x 1079, or 263 bits of effective entropy — and security. And, as we'll see below, this is only one of several places from which the PPC system obtains its security.

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) 2014 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 22, 2011 at 12:40 (976.55 days ago)Viewed 2 times per day