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.

I understand how to use the Grid multi-factor authentication as a user but how does it work technically? Specifically how can just a few letters from the grid be enough to decrypt any secret defined ahead of time or is this a more traditional challenge-response type of model?

EDIT: Link to Lastpass Grid Multifactor Authentication

share|improve this question
    
For those not familiar with it, can you provide a link, or a description? –  AviD May 11 '11 at 22:47
    
From a quick perusal, I'd point out that this is not a true second factor. Since the grid is not "something you have", but only "something you might have a copy of", there is no guarantee that you have the original, and only you have the only copy. –  AviD May 12 '11 at 21:15
    
@AviD the same is true of other Lastpass "something you have" authentication tokens, such as sesame which is just something you install on a thumbdrive. I suppose it's even possible someone would copy a yubikey. –  StephenPaulger May 13 '11 at 11:22
    
@AviD and the same thing is true of an RSA SecurID - the enterprise (and apparently RSA :( ) has the seed record, and the algorithm has been reverse-engineered, so they can be cloned. I don't think strong resistance to copying is a requirement for a "second factor". “Hard” cryptographic tokens are only required e.g. for NIST Level-Of-Assurance 4. I don't know if LastPass meets LOA 3, but resistance to copying isn't required AFAIK. –  nealmcb May 13 '11 at 21:27
1  
@AviD, OK, I'm curious enough to just make it a real question - we need one on this.... security.stackexchange.com/questions/3796/… –  nealmcb May 13 '11 at 21:59
show 1 more comment

3 Answers

up vote 3 down vote accepted

I don't know exactly what you mean by "decrypt any secret defined ahead of time" but it seems that it is a second challenge response system, and the 2nd factor (something you have) is your printed grid. Technically it works exactly as other similar systems work. On their part of the system, your grid is stored somewhere and is associated with your user identity. When logging in, the system chooses 4 random characters of the grid, you look them up and provide them. If there's a match there and a match on the password part, you are get logged in.

On further implementation details, the grid is nothing more that a 260 character string which is stored along your other details and 4 different characters are chosen each time to be asked.

share|improve this answer
    
Thanks. I guess what I was getting confused about was comparing this to the one-time-passwords (OTPs). My understanding of the OTPs is that they take the encryption key and encrypt it with the OTP but will only serve this out once. Lastpass still only sees an encrypted version of the key so they can't learn my secrets. In the multifactor grid case it appears that there is a shared secret (the key) which is known to Lastpass which initially concerned me. However since this is only used as a second factor I guess it is fine. –  snth May 12 '11 at 7:12
    
Your understanding of OTPs seems a little confusing. Yes,it can be like that but I'd say its a special implementation. Have you asked a question about that? If not you could, I'd like to hear more about this encryption it. On the Lastpass thing, I gather that the 'shared secret' you are talking about is the whole 260 character string of the grid? Then actually it is not a shared key. The key is the 4 letter word chosen each time. The 260 character string represents the keyspace of your key, not the key itself: You can choose any of 4 and a half billion keys based on that 260 character string. –  john May 12 '11 at 9:52
    
You're right, I meant to say that the shared secret is the grid, not the key. Apologies for the typo as well as the unclear explanation but I was writing in a hurry. I actually don't know how the Lastpass OTPs work, I was hypothesizing about how I thought it could work. –  snth May 12 '11 at 12:15
1  
@snth Are you sure it works offline? I will be very surprised if it does, and will have to revise my answer :) This thread seems to suggest otherwise: forums.lastpass.com/viewtopic.php?f=7&t=42359 –  john May 16 '11 at 9:13
1  
Thanks for than link @john. According to the lastpass user manual (helpdesk.lastpass.com/security-options/…) there is an option to allow offline access. Your link seems to suggest is that if you allow this then it is basically possible to circumvent the 2nd factor in an offline context. The only way the 2nd factor works is if you disallow offline access. –  snth May 16 '11 at 14:20
show 1 more comment

It looks like an additional challenge-response layer on top of the normal password you memorize, based on Grid Multifactor Authentication « LastPass User Manual

you can login to your LastPass plugin by providing your email and Master Password as usual. After you press Submit, you will be prompted to provide 4 random values off of your Grid:

share|improve this answer
add comment

Imagine a 2 dimensional chart with a curve drawn on it.

enter image description here

(Image from wikipedia user Vlsergey)

If you only knew one or two points on the curve you could not calculate the rest of the points on the curve, but given three points on the curve you could calculate any point on the curve.

This is a simplistic explanation of Shamir's Secret Sharing Scheme (Shamir of RSA fame) and is one way that the grid authentication could work. There are other secret sharing schemes.

share|improve this answer
    
Lastgrid's scheme is quite different in intent and mechanism from Shamir's scheme. They only ask for four alphabetic characters - not enough to hide any sort of other useful secret. They're just implementing a simple 2nd factor. –  nealmcb May 13 '11 at 21:14
    
Those four characters could be used to calculate the rest of the secret and thus verify it. I can't see how they could be securely verifying the selected characters otherwise. –  StephenPaulger May 16 '11 at 11:04
    
This scheme is simply one in which both sides know the whole grid, and use challenge-response to avoid revealing the whole thing on each verification attempt, so it is resistant to active attacks. No math involved.... –  nealmcb May 16 '11 at 17:32
    
So they store a copy of the grid in plaintext? –  StephenPaulger May 16 '11 at 23:02
1  
How they generate the numbers has no bearing on how they store them. I agree that they're probably used as a single string. I find it strange that they would stored the data insecurely, but given what is said here it seems unlikely they are using a secret sharing scheme. However I still think it would be a good way for them to store it. –  StephenPaulger May 18 '11 at 13:56
show 2 more comments

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.