Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

While in college I decided to have a randomly generated 16 character password. I used parts of that password in various sites. However, one of the sites was compromised so I had to change my password.

I now have a randomly generated passwords per site. As you can imagine, it was difficult to learn the passwords and I resorted to carrying them around until I had learned them. This was essentially a small piece a paper with random passwords in a row. Were these passwords compromised I'd be a VERY unhappy camper.

Suppose that I am determined on having a random set of passwords and not liking a row of passwords plainly visible. I was considering the option of instead creating a grid of randomly generated characters and using various sub strings in the data as passwords.

Here is a worked example:

Password Grid

bqzryXrMjs
wqpPcPW2tG
CYvLdxGsnZ
Hq9KDBJeN5
Z2v5H2BG6G
JYNyWGLqEa

Password: Start at (2,3). Use every other character from left to right, wrapping rows as necessary. Length 10.

Using these instructions I generate password:

9DJNZvHB6J

Note, that (2,3) was zero-indexed. Granted, those instructions are difficult to follow, but its just a skill to become better at. In practice I would use a larger grid and possibly a more complex pattern.

My question is how safe is this system. I know safe could mean lots of things. I'm not sure if cryptographically secure applies but I'm really just trying see if it would be reasonable to use this system to manage my passwords.

I can imagine a Bones episode where someone tracks my eye movements to determine what characters I'm reading... so suggestions like this are welcome but more practical/reasonable vulnerabilities are what I'm looking for.

Thanks!

EDIT #1

For the purposes of limiting the scope of the question suppose the following:

Passwords are of length 10
Grids are of dimension 20x20
The only instruction available is one similar describe above.  
    Start at (x,y)
    Use every other character from left to right, wrapping rows as necessary. 
    Length 10.

They are not allowed means that could be used to steal general private information such as a key logger, aggressive interrogation, etc.
share|improve this question

migrated from crypto.stackexchange.com Feb 13 at 18:50

This question came from our site for software developers, mathematicians and others interested in cryptography.

    
Don't try to learn about security from TV. Eye tracking is not a realistic concern. Observing what you're typing, far more so. –  Gilles Feb 13 at 22:53
2  
You're going to love this! Password Card. Carrying passwords are secure from hackers, but not governments or thieves who can torture you or rifle through your possessions. I used Password Card for a long time, but eventually had so many passwords I had to mark it up to keep track of which is which. I eventually switched to KeePass and now I don't know any of my passwords, but they are super secure. –  Chloe Feb 14 at 0:40
1  
In the same vein as Chloe, I came across grc.com/OffTheGrid.htm, which provides password grid with a much simpler algorithm to map the name of the website to a password. I don't use it myself though, I prefer a password locker. –  user60561 Feb 14 at 1:50

5 Answers 5

There are two sides to the security of your scheme. The first, of course, is "how secure is this?" First, apply Kerckhoff's maxim that states (paraphrased) "assume the attacker knows everything about your system except the key." If the attacker knows that you have this grid, and knows your every-other-letter scheme, and gets hold of your list that says "stackexchange.com (2,3)", he could produce your password. Break that apart into what he could learn, taking away different attributes:

  • If he doesn't know (2,3), but he knows the scheme and your grid, it's a simple brute force search of your grid.
  • If he knows (2,3), your grid, and that you use a transposition scheme, but doesn't know the details of your every other character scheme, he could brute force it with many tries.
  • If he knows your grid, and that you use a transposition scheme, and he learns any single password of any site protected by your scheme, he can reverse engineer your password scheme with very few tries.
  • If he doesn't know (2,3) and doesn't know you use a transposition scheme, but he knows your grid, it depends on how dedicated he is (and what valuables you are protecting.)
  • If he doesn't know your grid, but he knows your scheme, and he knows 100 other passwords from hacking 100 other sites, he could reconstruct your grid.
  • If he knows your scheme, and knows your password on a site, he might try other sites using random characters to prefix or suffix your 16 character password. Using your example, he might try www.mightybank.com : Carlos/09DJNZvHB6, Carlos/19DJNZvHB6, ... This likely wouldn't be practical for a blind attack, but if I was a malicious website operator who could test millions of passwords with impunity, I could easily try it out.

So the answer is that your scheme, the web-site starting coordinates, and the grid itself are all part of the data you must keep secret, not just the starting coordinates of the key.

The other side of your security is your risk: if you lose the grid, or you forget your rules, or become incapacitated, your passwords may not be recoverable.

share|improve this answer

If done right, the solution you suggested could be secure. In order to do so, however, you must be very diligent. You must not write down the coordinates used to generate a password, because if an attacker gets access to it, they can easily reproduce your passwords. You must not let anybody take a picture of your grid, because the finite number of permutations available on the grid allows an attacker to significantly lower the search space when brute forcing a password. You must be very careful not to loose the square, since doing so would cause you to loose all of your passwords. I wouldn't worry too much about complex attacks like reading eye-movements, unless you are storing something like nuclear missile arming codes, nobody will care enough to deploy something like that on you.

If you protect the grid correctly, you should be better off than just having a list of passwords. Guessing how the grid works is harder than just reading a password off of a list and all of the problems above also apply to a plain text list of passwords, leaving you with security that is at least a little bit better.

The solution you suggested could be further improved by incorporating some similar work done by GRC's Steve Gibson, which you can take a look at here - Perfect Paper Passwords. The example usage that the website gives is one time passwords for second factor authentication, but you could easily use the tool provided there to securely generate a grid to use for the scheme that you mentioned. The advantage of using the PPP tool are the following:

  1. The grid you generate will be a lot better. GRC goes to very great lengths to generate random numbers which means you'll get a grid that is less easy for an attacker to guess.
  2. It's reproducible. You can store the seed used to generate the grid and re-generate it in the future in case your wallet gets stolen, etc.
  3. You'll be better prepared to use it. If you listen to the Security Now podcasts listed on that page, Steve will give you all the tips/background info you could want. This means you'll be less likely to screw up and expose your passwords.

That being said, I don't really recommend using your suggested solution. The main reason is that it isn't super user friendly. If you want to just use a password, you have to get out the square, remember where to start to generate the correct password, and then manually transcribe the password into your computer. Added on top of that is all the mental overhead required to ensure that the square is protected correctly. To me, this sounds like something that will have a high enough barrier to entry that you will probably decide to use a less secure password instead of going through the trouble of using the square, leaving you with reduced security

Instead, I'd recommend using LastPass. LastPass provides a highly secure password store, with online backup. Note that LastPass does not directly store your passwords in their database. They store an encrypted blob containing the passwords that is encrypted/decrypted in the client application so they never see the actual passwords. Since they have page for web access, you can use LastPass securely from just about anywhere, even the browser on your phone. For a very small fee, you can even run a native LastPass that greatly improves the mobile experience. Using an application that automates all of the complicated parts of storing passwords means that you can have highly secure, per site passwords that you carry around with you in your pocket with little overhead to use them. You do need to make sure to use a very secure master password, but I would argue that this is still easier than trying to remember the coordinates on a grid used to generate the passwords for all of your sites.

share|improve this answer

Security Trade-off
Carrying the password grid on your person trades one type of security for another. Rather than something you have to remember, instead it's something you have to protect.

Humans appear to be better at securing the possessions than they are at securing the contents of their heads. This perhaps seems counter-intuitive, but evolution is on your side in this point. People tend to spill their secrets more often than they hand over precious objects.

Turning Up The Obscurity
The security of your paper password block if it falls into the hands of your attacker depends a bit on how you use it.

In it's current form and using the algorithm you expressed, it would be reasonably easy to brute-force with the possession of the pad. The attacker would simply start at the beginning of the password block and try various combinations of lengths and starting points until he arrived at the correct password. While there are lots of possibilities for him to sort through, it's easily automated and shouldn't take more than a few seconds for a computer.

Rather than simply reading characters in order, a better technique would be to "jump around". For example, use every other character starting at 3. Though that's pretty predictable. Or perhaps every 3rd character. Meh. Follow a Fibonacci sequence through the pad? Still very mathematical. Each of these might be tried by an attacker. You're just obscuring the pattern by interspersing it with noise.

RC4 famously uses a grid like this but uses the value of the item at the next cell you visit to determine where to move next. Maybe we could follow some sort of logic like that.

A Less Predictable Algorithm
We're going to use some arbitrary numbers. X and Y. Pick any numbers you want. Y can be negative.

So how about this for an algorithm. For any given password, start at position X. Now, follow the pattern below until you've generated enough characters for your password:

  1. Copy down the character at the current position. It's the the next letter in your password.
  2. Add Y to the number of characters you've copied so far. We'll call the result A.
  3. Look A spaces forward from your current position, wrapping as necessary. We'll call the value at that cell B. Convert it to an integer using any method you want. (e.g. A=1, B=2.. or perhaps A-E=1, F-J=2, etc. Anything will do).
  4. Take the calculated integer value of B and add it to your current position. The result is you new current position.
  5. Go to step 1.

The resulting algorithm jumps around the grid pretty unpredictably. Rather than following a set pattern, the pattern is determined by the surrounding contents of the grid. Someone who had the password and the grid would have a very, very tough time reversing your algorithm, so that's probably about as much secrecy as we can reasonably add at this level.

Hide in Plain Sight
The remaining problem is that what you're carrying around looks like a password. It's all random characters -- why would you have that. Instead, you want something that looks like you'd be carrying it around. Now that we have an algorithm for moving around a string in an unpredictable pattern, we can use much more prosaic text.

Print off something that looks like it belongs in your pocket. A list of a dozen names and dates, or perhaps a short block of sappy poetry. You want it to be unique, after all, it's your key. So don't just copy something off the Internet. But you want it to be examined and quickly discarded by an attacker.

Know Your Attacker
We've come up with something pretty hard-core. Your security here is quite a bit higher, but your difficulty in manually generating the password is too. So, whom are you defending against? If it's an oppressive government, then you're totally justified for doing this and more. If it's hackers whom you'll never come in contact with, then printing out the passwords on a paper saying "Super Secret Passwords" is just as sufficient. Somewhere in between? Then something simple will probably do.

I'd spend at least a bit of time making it look like something other than a password, though. The 3rd letter of each line in a grocery list, for example, will do.

share|improve this answer

The saying about passwords is that if you can remember it, it's not complicated enough.

Why not keep the list of passwords in a dedicated password manager software like KeePass? This will encrypt the file and let you generate very long and randomized passwords for each and every site. You can carry both the software and the file on a USB stick instead of a piece of paper, the single master password to decrypt the file is the only thing stored in your head.

share|improve this answer
4  
I would have to disagree with it having to be hard to remember. One of the easiest ways to gain entropy is by using a phrase instead of a word which is generally easier to remember than most short passwords. My favorite comic regarding this issue is xkcd.com/936. –  Travis Pessetto Feb 13 at 22:01
4  
@Daisetsu Your comment is almost entirely wrong. XKCD's entropy calculation is correct, and an attack over a password with 44 bits of entropy is not going to be over in minutes unless you focus a humongous number of computers on that task, especially if the password hash is a good one. –  Gilles Feb 13 at 22:51
1  
@Daisetsu you have to remember that even with a dictionary attack the English language is massive oxforddictionaries.com/us/words/…. –  Travis Pessetto Feb 13 at 23:10
3  
@Daisetsu: "correct" is not a noun. There is nothing requiring the words to be nouns. There is nothing requiring the phrase to be in English. And if users are picking high-ranked words they only have themselves to blame: picking by randomly opening a dictionary is a much better way. The calculation (44 bits of entropy) is predicated on picking words from a pool of 2048, so even if you do use high-rank words it is still very secure. And the components here are not characters, but words; as such, a dictionary attack is a brute-force method. Known phrases can be mitigated using generator apps. –  Amadan Feb 14 at 2:19
3  
This "answer" doesn't answer the question at all. It merely presents an alternative approach that the OP should consider. The OP asked about the security of their approach. –  mikeazo Feb 14 at 13:23

Given the assumptions, an attacker would have to pick a starting character, generate the 10 character password according to the process described, try it on the site. If it fails, repeat. After the 3rd attempt they would be locked out.

If we assume that on account creation you pick a good random starting place (in other words, every starting position is equally likely), then there are 20^2=400 possible starting positions. The probability of any one the attacker chooses being right is 1/400, so the probability that they get it right in three guesses is 3/400. A pretty low probability that you are likely willing to accept.

Where you might run into problems is if you start packing lots of sites into the same grid. Say you use the same grid for 50 sites. The attacker's probability of success is now (50)*3/400=0.375.

The good news is you can at least quantify the success chances of your attacker. If you have lots of accounts (and try to pack them all into one grid) you might be in trouble.

share|improve this answer
1  
I think you mean 1/400 + (399/400)*(1/399) + (399/400)*(398/399)*(1/398) instead of 3/400, but your approach is valid. I think limiting the instruction set is what really made it bad system. –  Carlos Bribiescas Feb 13 at 18:07
1  
Our attacker is dumb, they can't remember the starting position after each attempt so they may repeat :) –  mikeazo Feb 13 at 18:14
    
@Carlos actually what you wrote is equal to 3/400. In the second term the 399 on top and bottom cancel to get 1/400. Same thing for the 3rd term. –  mikeazo Feb 13 at 18:53
    
Hah, good point. –  Carlos Bribiescas Feb 13 at 19:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.