phc-discussions - A review per day, starting with Yarn

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date: Tue, 26 Aug 2014 21:22:30 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: A review per day, starting with Yarn

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I have some notes on all of the entries, and I am thinking of going
through them one at a time for discussion, one per day.  I was
thinking reverse alphabetical order would be more fair, since we tend
to pick on candidates starting with A more than those starting with T,
for example.

So, if anyone is interested in this idea, I'll carry it forward.  For
the next 24 hours, I'd like to discuss Yarn.

The author of Yarn is clearly a genius.  We have a lot of those around
here.  The code is awesome.  In 280 lines he encoded both AES and
blake2b, in addition to his algorithm!  I was blown away when I read it.

However, I'm not sure the Yarn author understands the password hashing
problem in as much detail as he should.  The biggest problem I have
with Yarn is this loop:

        for (i = 0; i < t_cost; i++) {
                if (i % m_step == m_step - 1) {
                        size_t idx = integerify(addr, m_cost);
                        for (j = 0; j < 16; j++) {
                                addr[j] = memory[idx][j] ^ state[1 %
par][j];
                        }
                        memcpy(memory[idx], state[1 % par], 16);
                        aesenc(state[0], addr);
                } else {
                        uint8_t tmp[16];
                        memcpy(tmp, state[1 % par], 16);
                        aesenc(state[0], tmp);
                }
                rotate_state(state, par);
        }

In short, it says to do AES encryption steps, but only write to memory
once every m_step steps.  IIRC, m_step is 72 by default, meaning Yarn
trickles out data at a pathetic pace, which is totally contrary to
memory hard security.

Other gripes I have are:

- - it has to have a very high t_cost to avoid TMTO.  With t_cost < 72,
no memory is over-written at all.  On the other 71, no memory is read
either.
- - with small memory reads pseudo-randomly through memory, it will run
slowly in external memory, at least once the m_step being 72 problem
is fixed.

The guy who posted Yarn showed up for a couple emails and left.  Maybe
he's just onto his next gig, but I feel like this guy has amazing
coding skills, and could knock security algorithms out of the park, if
he would just engage and learn a bit about what we need.

Bill
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJT/TLSAAoJEAcQZQdOpZUZpDEQAIwvh35Wdu4aYRgTDaBNc3hF
lu1iZKOm5DQro5tnr3+WBe16wO27/TWoYpKWhgCmiviWY7T8R6ACsKpL8n2LE9wV
D39qlQAN/JKKtblmD+ebFIxcerHineTBYf2NM4BlvsEf1gwto4i7vEZVgecSFoWe
ARzqDOGACPDkW6w1iTp6FUqQXkZjuhzkZ9aVPnUgSlUaco+y6Ov4jOuG5YcGdud/
GI1o9xa7lzyJtg1alx65HjakAVFUd4XTmMspPShkfXBowzTSo8CpOaKCBglWmzGq
/skDh5M85LGp4+S+QVIUlHIfG8/htH4loQzXR7/Rit40PPJ062Yi1qMXa+Sv+OMg
HK3DPuurztd1Js8U1DrSH1dGoSkXRtyfTvh0J+QI1zj7RWD5Enwh9GFGfEHO4sqD
K25Uc30+YsuDNBlj7kYBoD3TEoqtTE5Vv9zbiJkzQDs/flpk3rqLYqG/+NJh7xQf
c4O/YtG57Oif+j1rM5PXjt7Fztnc3amq/Oo0/d49xrl+F235sLjbXfH1UzgXmmi4
cnZ7J2XzoEsM10IWnsZkTbdsJS5RGrSJtKtzg3/yHVpi3VulJyMI0DEG+cMcbZtJ
4NzjJkFQrDue2e/v5e7kLmNQrt/oh8gVki6LYcwRFf1Na9j3rYlayP+OKexd1lfm
38wa8uxtVBhNHVlYzxxq
=8ihR
-----END PGP SIGNATURE-----