Scheme for protecting individual entries in a password manager

15 views
Skip to first unread message

Brien Brien

unread,
Dec 31, 2010, 11:45:33 AM12/31/10
to
All the password manager applications I've come across operate in an
all-or-none fashion- once the database is unlocked all the entries are
vulnerable if the machine happens to be compromised.

I'm trying to create a utility that will allow me to protect
individual entries via the use of a second device (eg iphone).

I will have a secret password that resides on the device only and is
used to decrypt entries in the password database on demand.

The scheme I've got so far is like so:

password manager M has a database of entries:
[uuid, title, encryptedpw, ...]

device D:
master pw Km


When the pw manager wants to decrypt an entry:
M->D: request key[uuid, title]
(Device may prompt user and display title depending on preferences)
D->M: Ke = HMAC(uuid, title, Km)
D: decryptedpw = AES-CBC(encrpytedpw, Ke)

Does this make sense? Are there any obvious flaws?

I'm resigned to the fact that if a password is used then it may be
stolen by badware.

What I'm aiming for is the ability to keep both high and low value
passwords in the same password database which may then be used to log
into low value sites without risking having high value ones stolen.

I'm also making the assumption that it's significantly harder for
someone to simultaneously pwn both my desktop machine and another
device.

Comments?

Jeffrey Goldberg

unread,
Dec 31, 2010, 1:47:10 PM12/31/10
to
Disclosure: I work for Agile Web Solutions, the makers of 1Password.

On 10-12-31 10:45 AM, Brien Brien wrote:
> All the password manager applications I've come across operate in an
> all-or-none fashion- once the database is unlocked all the entries are
> vulnerable if the machine happens to be compromised.

1Password comes close to what you want in that each individual record is
encrypted separately with a random key, K, that was created when the
data file was set up. The master password that the user enters is only
used to decrypt (using PBKDF2) this key. That key, K, is then retained
(with some obfuscation) in memory for only as long as the database
remains "unlocked". Individual items are decrypted only when needed
(and promptly wiped and freed when no longer needed). The idea here is
with a minimum amount of secret information decrypted at any time, it
reduces the chances of things getting dumped or written to swap.

The user is presented with an "all or none" metaphor, but that is not
what is going on behind the scenes (which is fully documented for the
users who wish to examine further).

None the less, it is true that when the K is available on a compromised
machine then everything in the database can be exposed.

> I'm trying to create a utility that will allow me to protect
> individual entries via the use of a second device (eg iphone).
>
> I will have a secret password that resides on the device only and is
> used to decrypt entries in the password database on demand.
>
> The scheme I've got so far is like so:
>
> password manager M has a database of entries:
> [uuid, title, encryptedpw, ...]
>
> device D:
> master pw Km
>
>
> When the pw manager wants to decrypt an entry:
> M->D: request key[uuid, title]
> (Device may prompt user and display title depending on preferences)
> D->M: Ke = HMAC(uuid, title, Km)
> D: decryptedpw = AES-CBC(encrpytedpw, Ke)
>
> Does this make sense? Are there any obvious flaws?

Unless you insist that you enter your password on your external device
for every single query, you will need to set up a trust relationship
between the password manager on your desktop and the app on your phone.
If the desktop is fully compromised, that the badware on your desktop
can get at those credentials. So I am not sure how this will improve
matters for you.

> What I'm aiming for is the ability to keep both high and low value
> passwords in the same password database which may then be used to log
> into low value sites without risking having high value ones stolen.

At the risk of advertising vaporware, the data format we use with
1Password does allow us to move in that direction. Indeed, on the
iPhone and iPod we do make use of separate security levels for items,
but we don't currently have this functionality in 1Password for Mac and
1Password for Windows.

So we have built some of the infrastructure for what you want I can't
make any promises about when we will make full use of that.

Cheers,

-j

--
Jeffrey Goldberg http://goldmark.org/jeff/
I rarely read HTML or poorly quoting posts
Reply-To address is valid

Brien Brien

unread,
Dec 31, 2010, 2:07:43 PM12/31/10
to
Jeff,

Please go away and find somewhere else to plug your product.
1Password does not do this and to say the database can't be dumped by
targeted malware would be a lie.

For anyone else following, yes, my description does assume that I've
already established a trust relationship between the desktop and the
device. I've already nailed that part down by doing a one time
pairing using SRP and a password.

Brien

Globemaker

unread,
Dec 31, 2010, 2:08:26 PM12/31/10
to
I like the two device idea. In addition, consider that the person also
has a brain as a third device. The person looks at the two screens and
uses hur training to interpret what is seen. One device shows a list
of partial passwords and the second device shows a different list of
partial passwords. The person then combines the chosen half passwords
in hur mind and types in the combined result: the password. The
training can be as simple or as elaborate as wanted, due to a set of n
techniques that are offered in the protocol.
full password..... welcome
half password 1: wloe
half password 2: ecm

training : alternating

MrD

unread,
Dec 31, 2010, 2:43:05 PM12/31/10
to
On 31/12/2010 19:07, Brien Brien wrote:
> Jeff,
>
> Please go away and find somewhere else to plug your product.
> 1Password does not do this and to say the database can't be dumped
> by targeted malware would be a lie.

Unfair.

It seems to me that Jeff's reply was on-topic for the list *and* for the
thread that you started. You posted to a public list; even if Jeff's
reply doesn't help you specifically, it might be helpful to others that
are interested in the thread - which (incidentally) doesn't "belong" to you.

--
MrD.

Brien Brien

unread,
Dec 31, 2010, 2:54:14 PM12/31/10
to

Not unfair:

Me: Password managers are flawed because the entire database can be
stolen if a machine is compromised.
Jeff: 1Password does this that and the other thing... blah blah
blah... all of which are irrelevant to the problem I've highlighted
and presented a solution for.

I'm looking for comments on the scheme and issues I'm trying to
address not on products that are fundamentally flawed in the exact way
I've highlighted.


Jeffrey Goldberg

unread,
Dec 31, 2010, 3:16:18 PM12/31/10
to
On 10-12-31 1:07 PM, Brien Brien wrote:

> Please go away and find somewhere else to plug your product.

Sorry it came across this way. I figured that negligibly few sci.crypt
readers would be interested using in a closed-source password management
system. I never thought I would "make a sale" here. But I thought that
they might be interested in the design.

You made claims about password managers work. Some (but not all) of the
technology you are looking for is in place within a password management
system that I am very familiar with. I provided information about that
technology.

> to say the [1Password] database can't be dumped by targeted


> malware would be a lie.

Correct. That would be a lie. I'm glad I didn't say that. Instead I said:

>> it is true that when the K is available on a compromised machine
>> then everything in the database can be exposed.

> For anyone else following, yes, my description does assume that I've


> already established a trust relationship between the desktop and the
> device. I've already nailed that part down by doing a one time
> pairing using SRP and a password.

Can that relationship be exploited by targeted malware on desktop to get
the entire database from the phone? If you claim that it can't, I would
be very skeptical. Unless (as I also said), you require very frequent
user interaction with the phone to allow it to give data.

I should say that I do like your idea overall. Though it looks like you
are storing the encryptedpw on both on M and D. Or was the last line of

> When the pw manager wants to decrypt an entry:
> M->D: request key[uuid, title]
> (Device may prompt user and display title depending on preferences)
> D->M: Ke = HMAC(uuid, title, Km)
> D: decryptedpw = AES-CBC(encrpytedpw, Ke)

Supposed to be take place on M?

Ari Silverstein

unread,
Dec 31, 2010, 3:48:27 PM12/31/10
to

Why wouldn't LastPass work for you?
--
Passwords, people, they are not just for game shows. If you refuse to
make the effort to remember a few long, diverse passwords, then don't
scream at me when your FICO is 496 and your bank accounts are zeroed
out.

Brien Brien

unread,
Dec 31, 2010, 3:59:20 PM12/31/10
to
> Supposed to be take place on M?
yes, typo.

Brien Brien

unread,
Dec 31, 2010, 4:00:20 PM12/31/10
to

malware on machine == all passwords may be stolen once unlocked.

still looking for comments on the proposed protocol. thanks.

Ari Silverstein

unread,
Dec 31, 2010, 4:49:40 PM12/31/10
to
On Fri, 31 Dec 2010 13:00:20 -0800 (PST), Brien Brien wrote:

>> Why wouldn't LastPass work for you?
>> --
>> Passwords, people, they are not just for game shows. If you refuse to
>> make the effort to remember a few long, diverse passwords, then don't
>> scream at me when your FICO is 496 and your bank accounts are zeroed
>> out.
>
> malware on machine == all passwords may be stolen once unlocked.

But you would have to have two machines compromised which is your
pretext as I understand it.

I would think that it would be easier to script your iPhone and your
local machine than LastPass server and your local machine.

Kristian Gjųsteen

unread,
Jan 1, 2011, 7:30:40 PM1/1/11
to
Brien Brien <brie...@gmail.com> wrote:
>I'm trying to create a utility that will allow me to protect
>individual entries via the use of a second device (eg iphone).

You have:

* A list of identifier-password pairs.
* Two devices M and D that can communicate.

The functionality you want:

* If M and D both agree, M should learn a password for a given identifier.

Your security goal:

* Unless M and D both are compromised, (a) a compromised M should learn
nothing about about any password that D does not want to reveal to him;
(b) a compromised D should learn nothing about any password.

["protocol" where M has a database of identifier-encrypted password
pairs, each pair encrypted with a per-identifier key; M asks D for the
per-identifier-key when it wants to reveal a password; D generates
per-identifier keys using by applying a KDF to a master key and the
identifier]

>Does this make sense? Are there any obvious flaws?

Goal (b) is trivially satisfied, since D does not have access to the
ciphertexts.

Goal (a) is also satisfied, provided the encryption provides
confidentiality against chosen plaintext attack. (Argument: We replace
the PRF by a random function, then we choose keys at random and remember
them instead of using the random function; now it is clear that unless M
asks for a key, he can learn nothing about the content of the ciphertext,
since the cryptosystem provides confidentiality.)

PS. Don't use AES-CBC, you want AES-GCM or AES-CCM or something similar,
since you really want integrity. What if D happens to reveal an
incorrect key.

Extra security requirement (c) if M asks for a password and accepts the
password as correct, the revealed password should be correct.

This seems somewhat unusual, but something like the following should do:
given a key and a ciphertext, it should be hard to find a second key
such that the ciphertext remains valid under this key. Most variants of
HMAC-then-encrypt should be OK; some variants of encrypt-then-HMAC could
satisfy that requirement, some variants not; I would hope CCM satisfies
that; I would worry about GCM.

A somewhat weaker alternative: given a key and a secret ciphertext,
it should be hard to find a second key such that the ciphertext remains
valid under this key.
--
kg

Jeffrey Goldberg

unread,
Jan 1, 2011, 7:39:53 PM1/1/11
to
On 10-12-31 3:49 PM, Ari Silverstein wrote:
> On Fri, 31 Dec 2010 13:00:20 -0800 (PST), Brien Brien wrote:
>
>>> Why wouldn't LastPass work for you?

>> malware on machine == all passwords may be stolen once unlocked.


>
> But you would have to have two machines compromised which is your
> pretext as I understand it.
>
> I would think that it would be easier to script your iPhone and your
> local machine than LastPass server and your local machine.

From my understanding of how LastPass works, Brien is correct here.
Although in normal operation LastPass communicates with a server where
the ciphertext is stored, a local copy of that is also maintained.

More importantly, a crucial element of Brien's scheme is that for the
phone to supply the key to the computer, human interaction (approval) is
required on the phone. This prevents a compromised desktop from simply
requesting decryption keys for everything in the database.

With LastPass if the master password in compromised on the desktop, then
malware could talk to the LastPass server and request everything.

Ari Silverstein

unread,
Jan 1, 2011, 8:21:17 PM1/1/11
to

Yes, you are right. I misread the individual element of Brien's
requirement.

Joseph Ashwood

unread,
Jan 2, 2011, 5:47:37 PM1/2/11
to
"Brien Brien" wrote in message
news:59ec5102-b37e-4467...@o14g2000yqe.googlegroups.com...

> D->M: Ke = HMAC(uuid, title, Km)

> Does this make sense? Are there any obvious flaws?

This is only a flaw that I realize because of some personal things right
now. Don't include the title in the hmac. This will allow the entries to be
renamed in a less complicated process.

This part goes against the common wisdom. As for using CCM or GCM instead,
in this case I think it represents a flaw. You actually don't want a MAC on
the password. The data transfer environment you'll be working in is
dependable, the only purpose a MAC would serve on this would be to provide
an oracle for the attacker. Since you'll be working in a fairly low entropy
environment any elimination of attacker advantage is valuable. If you want
something to protect the data integrity just use a hash (or error-correcting
code) across the ciphertext, this will only verify that the data was
stored/retrieved/sent/recieved correctly. I know this goes against the
common wisdom, typically you want the verification of a MAC, the existence
of a tiny oracle for the attacker is more than compensated for by the data
integrity protection, and you simply account for it in your entropy
estimation and the oracle effectively disappears. In a highly entropy
constrained environment (phones generally don't have access to much in the
way of entropy sources) the story is different, the oracle effectively
consumes some of your entropy and can actually make it easier for the
attacker. So even though it goes against the common wisdom, and I'm sure
others will try to correct me, using a MAC could be problematic from a
security standpoint.
Joe

Paul Rubin

unread,
Jan 2, 2011, 7:20:17 PM1/2/11
to
"Joseph Ashwood" <ash...@msn.com> writes:
> instead, in this case I think it represents a flaw. You actually don't
> want a MAC on the password. The data transfer environment you'll be
> working in is dependable, the only purpose a MAC would serve on this
> would be to provide an oracle for the attacker.

The usual concept of a MAC is that it's computed from a secret key that
the attacker doesn't possess. So how does the attacker use the MAC as
an oracle?

Ari Silverstein

unread,
Jan 2, 2011, 11:55:37 PM1/2/11
to
On Fri, 31 Dec 2010 11:54:14 -0800 (PST), Brien Brien wrote:

> I'm looking for comments on the scheme and issues I'm trying to
> address not on products that are fundamentally flawed in the exact way
> I've highlighted.

Clue: You're getting free advice. So sorry that it doesn't meet your
perfect criteria of delivering a point-to-point resolution to problems
you are incapable of solving but tuff shit.

Second clue: Acting out like a douchebag will only, at the end of the
day, get you douche fluids.

Sci.crypt as you already know is a stupendous resource. Tread lightly.
--
9ec4c12949a4f31474f299058ce2b22a

Joseph Ashwood

unread,
Jan 2, 2011, 11:54:26 PM1/2/11
to
"Paul Rubin" wrote in message news:7xoc7yn...@ruckus.brouhaha.com...

The attacker gains knowledge of another relation in the data. Assuming the
passwords being protected are high entropy, the only data is printability,
this is easily dealt with through even trivial compression. The ending MAC
data though provides verification of a valid password by providing the
relations:
StoredMAC = MAC(plaintext, MACKey)
MACKey = f(Ke) //Ke from original post, f() so far undefined
Ke = HMAC(uuid, title, Km) (from original post)

Since uuid is known, and Km is low entropy, the resulting relation is
valuable to an attacker as an oracle. Even a weak MAC (e.g. plain hash of
plaintext) would create a useful relation for the attacker, by adding the
key the process can be argued to be worse because it verifies Ke without
accessing the password check, providing a shortcut oracle.
Joe

Kristian Gjųsteen

unread,
Jan 3, 2011, 3:25:13 AM1/3/11
to
Joseph Ashwood <ash...@msn.com> wrote:
>Km is low entropy

Why would Km be low entropy?

--
kg

Brien Brien

unread,
Jan 3, 2011, 10:48:37 AM1/3/11
to
On Jan 1, 7:30 pm, Kristian Gj steen <kristiag+n...@math.ntnu.no>
wrote:

thanks for the anaylsis kristian!

Brien Brien

unread,
Jan 3, 2011, 10:51:34 AM1/3/11
to

Joseph,

Yes, that was my thinking. I'd rather have something harder to attack
than the validation.

The reason for including the title in the HMAC is so that it can't be
spoofed when presenting the confirmation prompt to the user on D.

It may be a bit of a pain, but I can't think of a simpler way to
prevent spoofing.

Thanks,
Brien

Brien Brien

unread,
Jan 3, 2011, 10:53:20 AM1/3/11
to

Looks like you know a thing or two about being a douchebag, Duane.

http://groups.google.com/group/alt.comp.freeware/browse_thread/thread/b16270574d3f99e9/1268b4e3d34d504b

Brien Brien

unread,
Jan 3, 2011, 10:54:57 AM1/3/11
to
On Jan 3, 3:25 am, Kristian Gj steen <kristiag+n...@math.ntnu.no>
wrote:

> Joseph Ashwood <ashw...@msn.com> wrote:
> >Km is low entropy
>
> Why would Km be low entropy?
>
> --
> kg

Km _should_ be high entropy, but it's going to be user chosen so my
thought is to leave out verification of the decrypted password.

Ari Silverstein

unread,
Jan 3, 2011, 1:30:35 PM1/3/11
to

You don't want to take me on and now you have had your warning.

Kristian Gjųsteen

unread,
Jan 3, 2011, 1:31:11 PM1/3/11
to

Why should the user choose Km? Why not store it on the device, possibly
encrypted with a (user-selected) password if that seems sensible.

In my experience, typing high-entropy passwords on a typical mobile
phone is awkward. Furthermore, the security usability of password-only
systems is fragile.

--
kg

Ari Silverstein

unread,
Jan 13, 2011, 2:40:15 PM1/13/11
to
Reply all
Reply to author
Forward
0 new messages