[openssl.org #3505] rewrite c_rehash in C

[Timo Teräs via RT]

Find a C version (which I have written) of the utility at:
http://git.alpinelinux.org/cgit/aports/plain/main/openssl/c_rehash.c

It performs several magnitudes faster. Rehashing full ca-certificates
list (especially on embedded systems) is now under 0.01 seconds instead
of several seconds (up to tens of seconds on slower boxes).

______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

[Salz, Rich]

Post by Timo Teräs via RT
http://git.alpinelinux.org/cgit/aports/plain/main/openssl/c_rehash.c

That's pretty cool. We'd need to modify it to not use the XXXat functions or fnmatch, but definitely something we should consider for a future release.

--
Principal Security Engineer
Akamai Technologies, Cambridge MA
IM: ***@jabber.me Twitter: RichSalz

���H���7��m����
)z{,��� �ޖ�fz{Lj)b����)z{,�ׯ�����h�

[Salz, Rich]

Don't rush. It'll be a while until (or if) we switch over. Neat job tho.
Perhaps it should be merged into the openssl command?
(see https://github.com/akamai/openssl/tree/rsalz-monolith)
--
Principal Security Engineer
Akamai Technologies, Cambridge MA
IM: ***@jabber.me Twitter: RichSalz

______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

[Timo Teras]

On Tue, 26 Aug 2014 12:50:49 -0400

Post by Salz, Rich
Don't rush. It'll be a while until (or if) we switch over. Neat job
tho. Perhaps it should be merged into the openssl command?
(see https://github.com/akamai/openssl/tree/rsalz-monolith)

I wrote the code about 8 months ago - and did not bother to file a
ticket until I saw the other ticket about shell c_rehash. I just wanted
to polish the code to the point that it would be acceptable.

And exactly this feedback is what I sought for. Yes, making it an
openssl subcommand would make sense (assuming it supports c_rehash
symlink too). I'll give some additional thought for this approach.

Thanks,
Timo
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

[Timo Teras]

On Tue, 26 Aug 2014 10:12:06 -0400

Post by Salz, Rich

Post by Timo Teräs via RT
http://git.alpinelinux.org/cgit/aports/plain/main/openssl/c_rehash.c

That's pretty cool. We'd need to modify it to not use the XXXat
functions or fnmatch, but definitely something we should consider for
a future release.

It's fairly simple to get rid of them both. I write it originally for
Linux without caring too much for portability. But I'm willing to fix
these issues. I'll try to fix these matters within few days. Please do
tell if there's anything else that might need changing.

Thanks,
Timo
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

[Salz, Rich]

BTW, as you work on this, also take a look at RT items 2272 and 2973 :)

______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

[Timo Teräs via RT]

Updated c_rehash.c based on feed back from the mailing list and Rich
Salz.

Would be nice to get additional review. It is not yet a patch for
'openssl' subcommand, but this is on the list. Just posting current
progress.

Most notable changes:
- removal of non-portable libc usage such as fnmatch(), *at() functions
- atomic update of hashes is improved, but not perfect. as in symlinks
are only touched if needed. trying to take care of all possible race
conditions looks tricky, and probably not feasible.
- added 'crt' extension
- hashes only files containing exactly one certificate or CRL. this is
1) because openssl library core checks only the first cert, and 2)
distros often create ca-certificates.crt containing *all*
certs, as this now matches known extensions it would easily make
openssl core break when all symlinks point to this same .crt file.
- code to create old style hashes is there, but no command line switch
parsing is added yet

also some other minor cleanups and changes are done too.

Feedback would be appreciated.

Thanks,
Timo

[Salz, Rich]

Great work!

--
Principal Security Engineer, Akamai Technologies
IM: ***@jabber.me Twitter: RichSalz
���H���7��m����
)z{,��� �ޖ�fz{Lj)b����)z{,�ׯ�����h�

[Mike Frysinger]

Post by Timo Teras

Post by Salz, Rich

Post by Timo Teräs via RT
http://git.alpinelinux.org/cgit/aports/plain/main/openssl/c_rehash.c

That's pretty cool. We'd need to modify it to not use the XXXat
functions or fnmatch, but definitely something we should consider for
a future release.

It's fairly simple to get rid of them both. I write it originally for
Linux without caring too much for portability.

the XXXat functions are in POSIX and are not specific to Linux or glibc, so they
are technically portable. but openssl tries to work on older/crappier systems
that do not follow or stay up to date with POSIX ...
-mike

[Viktor Dukhovni]

Post by Salz, Rich

Post by Timo Teräs via RT
http://git.alpinelinux.org/cgit/aports/plain/main/openssl/c_rehash.c

That's pretty cool. We'd need to modify it to not use the XXXat
functions or fnmatch, but definitely something we should consider
for a future release.

Does this version fix the atomicity problems of the original?

The Perl version deletes all the symlinks and then rebuilds them,
leaving a time window during which verification fails.

The algorithm should be improved to never delete links which are
subsequently recreated.

[Timo Teras]

On Tue, 26 Aug 2014 17:19:24 +0000

Post by Viktor Dukhovni

Post by Salz, Rich

Post by Timo Teräs via RT
http://git.alpinelinux.org/cgit/aports/plain/main/openssl/c_rehash.c

That's pretty cool. We'd need to modify it to not use the XXXat
functions or fnmatch, but definitely something we should consider
for a future release.

Does this version fix the atomicity problems of the original?
The Perl version deletes all the symlinks and then rebuilds them,
leaving a time window during which verification fails.
The algorithm should be improved to never delete links which are
subsequently recreated.

I almost answered "it's fixed". But it's not. IIRC, the version had it
fixed, but it did not handle hash collisions nicely. This certainly is
possibly to do, but needs some extra care when there's collisions and
the entries need renaming instead of deletion.

The time window is certainly a lot less in C-version, but it still
exists. I'll look into fixing this too.

Thanks.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-***@openssl.org
Automated List Manager ***@openssl.org

[Viktor Dukhovni]

Post by Timo Teras

Post by Viktor Dukhovni
The algorithm should be improved to never delete links which are
subsequently recreated.

I almost answered "it's fixed". But it's not. IIRC, the version had it
fixed, but it did not handle hash collisions nicely. This certainly is
possibly to do, but needs some extra care when there's collisions and
the entries need renaming instead of deletion.
The time window is certainly a lot less in C-version, but it still
exists. I'll look into fixing this too.

The collision case is tricky when a colliding trust-anchor is
deleted whose index suffix is not the largest. I'd be tempted to
symlink it to the remaining colliding certificate with the highest
index:

Before:

X.0 -> retired CA
X.1 -> retained CA

After:

X.0 -> retained CA
X.1 -> retained CA

And leave it that way for some time. On each run, if the highest
numbered index is duplicated by a lower-numbered index whose lstat(2)
age is sufficiently high (5 minutes or more?), that index can be
deleted (garbage collection). That might create a situation in
which we have:

X.0 -> CA1
X.1 -> CA1
X.2 -> CA2
(X.3 -> CA1 deleted)

In that case, update all but the first link to any fixed target to
point to the highest retained index.

X.1 -> CA2.

Leaving the invariant condition that at the end of each run at most
the last CA is duplicated. In steady-state this eliminates redundant
links, but avoids exposing verifiers to race conditions.