Message-ID: <20150716084828.GA5408@openwall.com>
Date: Thu, 16 Jul 2015 11:48:28 +0300
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: patents

Hi,

Earlier this year, I became aware, from Jeremy Spilman, of 2 patents
that might (or might not, I am not a patent lawyer) apply to purposeful
use of yescrypt's ROM as a secret.  My understanding is that they do not
apply to uses of a ROM for port-hardness, which is what I am primarily
proposing it for.

One of these patents is Jeremy's own on what he calls Blind Hashing,
already discussed in here.  (It made me pretty sad and angry at first,
as I think it's a good idea that is a pity to have taken away from the
larger community until the patent expires.  Also, obviously several
people were thinking of similar approaches, not just Jeremy.)

IIRC, the Blind Hashing patent talks specifically about looking up extra
"salts", so it is unclear to me (not being a patent lawyer and not
having read the patent closely) if this language applies to simultaneous
use of a RAM and ROM like yescrypt does where no intermediate tiny value
(salt-like) is ever derived.  Hopefully not.  For upgraded hashes, with
g > 0, there are obviously tiny intermediate values - the old,
pre-upgrade hashes.  I don't know if it fits under "salts" per that
patent or not.  But even if it does, it shouldn't apply when the ROM
isn't being used as a secret, but is used e.g. for port-hardness.

The other patent, which I also haven't read closely, covers an idea
expressed in IIRC a Microsoft Research paper from several years ago.
In the paper, it's essentially the same idea Steve Thomas proposed
shortly before Passwords12 - a large ROM on a system connected at low
bandwidth just sufficient for defensive use but not for quickly
downloading the ROM.  (I don't have that paper reference handy at the
moment.  I may dig it up and post later, or Jeremy may.)

In both cases, the number of lookups was intended to be low - just
sufficient to hopefully prevent at least 1 of them (in each one hash
computation) from completing when an attacker has only a portion of the
ROM (e.g. only 1/4 of it), for most candidate passwords tested.
In yescrypt's use of ROM, the number of lookups is a lot higher, as
needed to provide port-hardness.

Overall, I feel these patents do not directly apply to yescrypt's ROM,
and not at all to its primary intended use, yet I felt I needed to post
about them in here.  I'd appreciate advice on whether/how to mention
related yet likely not directly applying patents like that in a revised
yescrypt specification document.

Alexander

Powered by blists - more mailing lists