9

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

snth
  • 965
  • 1
  • 9
  • 10
  • 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. – Stephen Paulger 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.... http://security.stackexchange.com/questions/3796/how-is-two-factor-authentication-typically-defined – nealmcb May 13 '11 at 21:59
  • The nice thing about the Yubikey is that you **can** generate your own secret key and leave it unknown to the yubico servers if you wish. It probably wouldn't work with LastPass then... but at least then you know you've got the only copy of your key. To clone your key, someone has to know the secret key, plus the values of the internal counters. This is highly unlikely. – TrinitronX May 19 '11 at 22:08

4 Answers4

3

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.

john
  • 10,998
  • 1
  • 36
  • 43
  • 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 07: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 09: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
  • I guess what I was trying to understand and what got me confused is how this works in an offline context. I understand the Challenge-Response model when you are online but Lastpass claims that you can still access you vault when you are offline (I haven't tested this). Any guesses for how the grid authentication works when you are offline? – snth May 16 '11 at 07:02
  • 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: http://forums.lastpass.com/viewtopic.php?f=7&t=42359 – john May 16 '11 at 09:13
  • 1
    Thanks for than link @john. According to the lastpass user manual (http://helpdesk.lastpass.com/security-options/grid-multifactor-authentication/) 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
1

Wow. Too many overly smart people here showing off their knowledge of security systems but everyone seems to be getting it wrong or missing the concept.

One person refers to OTP, which typically means One Time Pad and is an encryption technique, but mistakenly calls it One Time Password, which is a totally different thing entirely.

The Grid Multifactor Authentication used in lastpass has nothing to do with Encryption. It's an authentication mechanism. It falls into the "something you have" category because you don't memorize it and therefore it is not "something you know".

The bottom line is that it is just a second very long password and it is akin to other companies or websites asking you originally for a secret word or phrase and then when logging in they ask something like: "type the 3rd, 5th, and 7th letters of your secret".

With enough data collection, a hacker would be able to know the whole word or in the case of the Grid, the whole grid, but hopefully you have replaced it after using up a significant amount of it (I'd go with about 25% at the highest).

Since the original post is now over 9 years old, I'm posting this not for the benefit of the OP, but for anyone else that may stumble across this as I did.

ubiquity
  • 11
  • 1
0

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:

nealmcb
  • 20,693
  • 6
  • 71
  • 117
-1

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.

Stephen Paulger
  • 191
  • 7
  • 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. – Stephen Paulger 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? – Stephen Paulger May 16 '11 at 23:02
  • That's my assumption, based on them saying "Grid of randomly generated characters", and in accord with John's answer. Seems much better than having some structure to the grid, which would reduce its entropy. – nealmcb May 17 '11 at 14:18
  • 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](http://forums.lastpass.com/viewtopic.php?f=7&t=42359) 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. – Stephen Paulger May 18 '11 at 13:56
  • Good point about how it should be stored! So seems like it could be stored via Shamir's scheme - n = 260, k = 4. Do you know how much storage that would take, what software can do it, etc? – nealmcb May 18 '11 at 16:52