OpenPGP: Precompute S2K message schedules for short password-lengths

[koto]

From coruus@gmail.com on July 14, 2014 00:28:23

e2e.openpgp.IteratedS2K.getKey is slow for large c. Really really slow. 25 seconds for SHA2-512 at c=255.

Something easy to do for, e.g., 64-byte blocksize hashes:

For passwords < 56 bytes, create an array of all the blocksize-filling salted_passphrase rotations; then absorb these blockwise until the bytecount condition is met. goog.Crypt.Sha1 has a fast-path for blocksize calls: 25% speedup in this case. Don't think that goog.Crypt.Sha2 or Sha2_64bit do; but probably better, in any event, to import the code and use computeChunk_ directly for the repeated steps.

Even better:

Precompute message schedules for all rotations; then do as above, but only applying the MD update steps. Relative workfactor is from .57 to .66 for SHA instances at c=255. Cost breakdown attached.

(The bitops numbers are irrelevant here; the "p(rocessor)ops" numbers are relevant, but the operation costing may not be right for V8 -- the model I drew these numbers from was intended for (and verified on) a specific processor.)

Attachment: s2k.markdown

Original issue: http://code.google.com/p/end-to-end/issues/detail?id=113

[koto]

From coruus@gmail.com on July 13, 2014 21:24:41

[koto]

From coruus@gmail.com on July 13, 2014 21:24:41

[koto]

From coruus@gmail.com on July 17, 2014 11:04:14

And...two preliminary patches to goog.crypt.shaX; somewhat faster according to Closure's benchmarks. (And the initial work for prescheduling.)

Attachment: CLOSURE.patches

[koto]

From evn@google.com on July 17, 2014 16:52:13

Cc: adhintz@google.com tha...@google.com

[koto]

From evn@google.com on July 17, 2014 17:03:08

Labels: -Priority-Low Priority-Medium Performance Component-Logic

[koto]

From evn@google.com on July 18, 2014 14:04:04

we are getting the external contribution agreement stuff ready. but this patch seems very useful, thank you very much! :)

Status: Accepted

[koto]

From adhintz@google.com on July 23, 2014 15:59:01

Status: Started
Owner: adhintz@google.com

[koto]

From adhintz@google.com on July 24, 2014 00:21:18

Nice performance improvement! Two questions:

1. Are you going to submit the Closure SHA patches to the Closure project directly, or would you like us to handle that for you?
2. Why restrict this technique to passwords < 56 bytes?

I integrated your patch into the main e2e.openpgp.IteratedS2K.prototype.getKey() and perform the zero-prepending when needed. Here's a preview of the code in case you'd like to take a look:

e2e.openpgp.IteratedS2K.prototype.getKey = function(passphrase, length) {
var salted_passphrase = this.salt_.concat(passphrase);
var count = this.count_;

if (count < salted_passphrase.length) {
count = salted_passphrase.length;
}

var block_size = this.hash.blockSize;
var reps = goog.math.safeCeil(block_size / salted_passphrase.length) + 1;
var repeated = goog.array.flatten(goog.array.repeat(salted_passphrase, reps));

var num_zero_prepend = 0;
var hashed = [], original_length = length;
while (length > 0) { // Loop to handle when checksum len < length requested.
this.hash.reset();
// TODO(adhintz) If num_zero_prepend > 0, align hash input to block_size.
this.hash.update(goog.array.repeat(0, num_zero_prepend));
var i = 0;
while (i + num_zero_prepend < count) {
var offset = goog.math.modulo(i, salted_passphrase.length);
var size = (block_size < count) ? block_size : count;
this.hash.update(repeated.slice(offset, offset + size));
i = i + size;
}
var checksum = this.hash.digest();
length -= checksum.length;
goog.array.extend(hashed, checksum);
num_zero_prepend += 1;
}
return hashed.slice(0, original_length);
};

[koto]

From coruus@gmail.com on July 24, 2014 01:18:49

That looks very much better!

Re 1: Closure pull request is here: google/closure-library#322 Re 2: Nope. No need to limit length in this case.

(The reason for the limit -- and the messy code structure -- was that I was working on precomputing message schedules for SHA2-256 and 56+8=64 = 1 block. Which is easy to reason about, and a convenient memory limit. But I haven't had the time to finish that yet... The repetition trick is more general, as you've noted.)

[koto]

From coruus@gmail.com on July 24, 2014 18:21:04

And...a link to the aforementioned prescheduling code. More of a performance impact than I had thought, it appears. coruus/e2e@909622d

[koto]

From coruus@gmail.com on July 24, 2014 18:24:40

Just as a note, it depends on the latest Closure SHA-256 patch here: https://github.com/coruus/closure-library/tree/sha1-sha2_32b

[koto]

From adhintz@google.com on July 25, 2014 11:31:58

By the way, two relevant changes I pushed recently:

1. The initial repeated passphrase array. This gives a 50% performance improvement: https://code.google.com/p/end-to-end/source/detail?r=a89c6d160505ad76f0aa8da76e9896e97a91ee91 2) Align initial hash input when there are prepended. This reduces the execution time by approximately 7% for a typical case such as requesting 40 bytes using sha1. https://code.google.com/p/end-to-end/source/detail?r=bc066805941b86dcf23d2eee3fe81def5cb1ba01 I'll take a look at your precomputed message schedules code.

[koto]

From coruus@gmail.com on July 29, 2014 09:05:20

And, finally, precomputed message schedules for SHA2-256. About ~3.5x faster for SHA2-256, for c=255. Patch attached. Performance test in s2k_test.html

For deriving a 32-byte key, SHA2-256 is now ~7.5x faster than SHA1. Patch therefore attached to modify defaults for exportable private keys and SKESKs.

(Some functions appear to request more than 32 bytes of output from e2e.openpgp.IteratedS2K.getKey. These seem to be E2E-internal; I haven't modified them because it looks like some work is going on to use scrypt, which will be wonderful.)

(This depends on parts of my Closure SHA pull request; a patch that rolls up that request is attached for convenience.)

Attachment: s2k_prescheduling.patch s2k_changedefaults.patch closure-sha.patch

[koto]

From adhintz@google.com on July 30, 2014 21:30:08

Thanks! After the Closure pull is accepted, please let us know so we can accept your new s2k patches.

[coruus]

And: an updated Closure PR is here: google/closure-library#391

(Looking through the commits: Evidently the JS engine on some revs of the Kindle Fire was failing to handle the type-coercions correctly. If you can get me more details on what the problem was, I'd appreciate it.)

CC @dlg-yahoo

[koto]

Any updates on this?

[coruus]

Status of Closure?
On Wed, Jun 10, 2015 at 10:21 AM Krzysztof Kotowicz <
notifications@github.com> wrote:

Any updates on this?

—
Reply to this email directly or view it on GitHub
#150 (comment).

[sirdarckcat]

coruus, can you send this as a pull request?

coruus/e2e@909622d

not sure if it's ready or you had something pending