[Cryptography] Recommendations for short AES passphrases

ıuoʎ yonjah at gmail.com
Sat Sep 17 08:01:43 EDT 2016

I just noticed my reply was not sent to the list so I'm forwarding it  -
On Sat, Sep 17, 2016 at 3:24 AM, Jon Callas <jon at callas.org> wrote:
> I read what you're doing and my question is -- what problem are you actually trying to solve? You need to examine that, first and have a clear description. It's very easy to get lost in the weeds of details and lose sight of what you're doing.
> Let me rewind all the way to the top -- a password (passphrase). Breaking that password, by guessing it or stealing it short-circuits everything else.
> A password KDF like PBKDF2 has two purposes -- one is to whiten the password out to a full key size (if you need me to describe what I mean by "whiten" just say so), and also to slow down a brute force key search.
> The iteration count slows down the search. We can also have a long discussion of that, in general. But 1000 is way too low. You really want to be doing much more. There's nothing wrong with having a significant fraction of a second in wait time there, but this also gets us back to what problem you're trying to solve.
> You're asking us about solutions without stating the problem. The discussion might be interesting, but it's only going to help you by luck.
>         Jon

Thanks Jon and John For your reply.
I guess I wasn't very clear so let me try and give some more
information about the situation.

it's not a system I'm responsible for It's just some online service I
became aware of.
Since it's currently extremely broken, I don't want to reveal too much
information to identify the actual service. I'm also not 100% sure
about the reasoning for using a weak passphrase in the first place.

But lets assume you have an online Pokemon location sharing service.
So users can jump to your site share the location of the Pokemon they
just found.
When they do that a random salt and key is generated on their device
and the data is encrypted only the data and salt is sent to the server
so the server can't access the Pokemon location.
the user receive a link she can exchange with other Pokemon hunters.
The URL has a text representation of the key in the hash part (after#)
so its never sent to the server but allows to decrypt the data to who
ever has the full URL.

As you can see sharing the key is part of the requirements I don't
think there is any way around it or that PBK encryption will be a good
match here. The key is unique and not controlled or has to be
memorised by the user. But I think it has to be short and simple
enough so it can be typed on a mobile phone or dictated to someone.

The Pokemon location is only good for a week since after that the
Pokemon will probably be in a completely different location.
So if an attacker can't break the encryption in a week it is not worth trying.
Value wise the data is probably more valuable than Pokemon location
but not much.
As I mentioned I can assume 100$ per share is probably a very high
assumption but I doubt its actually worth more than 10$ remember this
is data the user intended to share with strangers any how, but we
still don't want to make it public.

So I know for any powerful adversary a 8 chars BASE58 will be probably
easy enough to crack, If I did the math properly there should be ~125
Trillion possibilities for the passphrase.  If I assumed a medium
adversary can try a Million keys a second it would still take longer
than 3 years to go over the entire key space.
So if I use a slower KDF like (1000 rounds of PBKDF2) that will be 3,000 years.
When I cracked the original encryption (that only used md5 for KDF) I
got ~ 10,000 attempts per sec (KDF and FULL AES decryption), so I hope
the numbers here are secure enough to represent medium adversary
(which has at least 100 times more computing power than I have).
Of course we can always increase the KDF rounds but I think 1000 is
probably the limit performance wise, they might be willing to go 2000
rounds but having 2 seconds extra lag on loading time is probably a
bit too much (remember KDF is running on the client which might be a
mobile phone with a weak cpu)

Looking at the cold math It feels like 8 chars are secure enough for
the mentioned requirements, for me it still feel quite too short.

So is it actually secure enough or am I missing something.
Is there any better way to generate short key that will still be
somewhat secure.
I can assume there might be some gpu resistant hashing algorithms that
might be a better candidate for the hash (maybe scrypt?) that might be
an option but I knwo there current crypto lib (there using CryptoJS
which I'm not sure is very good one) supports PBKDF2 so if that's good
enough I think its easy switch for them.

I also have some wonders about the PRNG being used but that's probably
on another topic once I'll get the base key length sorted.

More information about the cryptography mailing list