Everything

php

[RFC] RFC4648 encoding

php.internals

Scott Arciszewski

10 years ago

PHP already offers bin2hex()/hex2bin() and base64_encode()/base64_decode().
This covers part, but not all, of RFC 4648.

I'd like to extend the coverage to include, at minimum, Base32.

I'd also like to make these functions to be written to resist cache-timing
attacks (i.e. when used to encode/decode encryption keys for long-term
storage). Userland PoC: https://github.com/paragonie/constant_time_encoding

http://blog.ircmaxell.com/2014/11/its-all-about-time.html

These modifications can either be made in-place (at a negligble cost on the
scale of nanoseconds) or they can be an alternative implementation. i.e.

* bin2hex_ts()
* base64_encode_ts()
* base32_encode_ts()

Does anyone have any questions or concerns?

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com>

Yasuo Ohgaki

10 years ago

Hi Scott,

On Wed, Mar 23, 2016 at 3:29 AM, Scott Arciszewski <scott@paragonie.com> wrote:

> PHP already offers bin2hex()/hex2bin() and base64_encode()/base64_decode().
> This covers part, but not all, of RFC 4648.
>
> I'd like to extend the coverage to include, at minimum, Base32.
>
> I'd also like to make these functions to be written to resist cache-timing
> attacks (i.e. when used to encode/decode encryption keys for long-term
> storage). Userland PoC: https://github.com/paragonie/constant_time_encoding
>
> http://blog.ircmaxell.com/2014/11/its-all-about-time.html
>
> These modifications can either be made in-place (at a negligble cost on the
> scale of nanoseconds) or they can be an alternative implementation. i.e.
>
>     * bin2hex_ts()
>     * base64_encode_ts()
>     * base32_encode_ts()
>
> Does anyone have any questions or concerns?

Sounds good to me and I would like to see these in next release.

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

Andrew Faulds

10 years ago

Hi Scott,

Scott Arciszewski wrote:

> PHP already offers bin2hex()/hex2bin() and base64_encode()/base64_decode().
> This covers part, but not all, of RFC 4648.
>
> I'd like to extend the coverage to include, at minimum, Base32.

Sounds good. It fills a gap and would doubtless be useful for some
applications.

This made me wonder if we should add a generalised arbitrary-base with
arbitrary character set pair of encoder and decoder functions. But
that's a niche use case, they're simple enough to do in userland.

> I'd also like to make these functions to be written to resist cache-timing
> attacks (i.e. when used to encode/decode encryption keys for long-term
> storage). Userland PoC: https://github.com/paragonie/constant_time_encoding
>
> http://blog.ircmaxell.com/2014/11/its-all-about-time.html
>
> These modifications can either be made in-place (at a negligble cost on the
> scale of nanoseconds) or they can be an alternative implementation. i.e.
>
>      * bin2hex_ts()
>      * base64_encode_ts()
>      * base32_encode_ts()

Unless there's a huge, and actually problematic, performance difference,
then I'd suggest we replace our existing implementations, rather than
adding new functions. This way existing code potentially benefits from
the security improvement, we don't give developers an unncessary choice,
and there's no extra clutter.

One more thing, only vaguely on-topic: the base64_decode/_encode
functions don't let you specify whether you want "base64" or the variant
"base64url", they always use the former. You can use a regular
expression or strtr() to convert the input/output, of course, but it
would be more efficient (and perhaps for security purposes, less likely
to allow timing attacks?) if there was built-in support. So, should we
add a parameter to these functions to specify if the base64url variant
is to be used?

Thanks for your proposal!

--
Andrea Faulds
https://ajf.me/

Scott Arciszewski

10 years ago

On Tue, Mar 22, 2016 at 7:11 PM, Andrea Faulds <ajf@ajf.me> wrote:

> Hi Scott,
>
> Scott Arciszewski wrote:
>
>> PHP already offers bin2hex()/hex2bin() and
>> base64_encode()/base64_decode().
>> This covers part, but not all, of RFC 4648.
>>
>> I'd like to extend the coverage to include, at minimum, Base32.
>>
>
> Sounds good. It fills a gap and would doubtless be useful for some
> applications.
>
> This made me wonder if we should add a generalised arbitrary-base with
> arbitrary character set pair of encoder and decoder functions. But that's a
> niche use case, they're simple enough to do in userland.
>
> I'd also like to make these functions to be written to resist cache-timing
>> attacks (i.e. when used to encode/decode encryption keys for long-term
>> storage). Userland PoC:
>> https://github.com/paragonie/constant_time_encoding
>>
>> http://blog.ircmaxell.com/2014/11/its-all-about-time.html
>>
>> These modifications can either be made in-place (at a negligble cost on
>> the
>> scale of nanoseconds) or they can be an alternative implementation. i.e.
>>
>>      * bin2hex_ts()
>>      * base64_encode_ts()
>>      * base32_encode_ts()
>>
>
> Unless there's a huge, and actually problematic, performance difference,
> then I'd suggest we replace our existing implementations, rather than
> adding new functions. This way existing code potentially benefits from the
> security improvement, we don't give developers an unncessary choice, and
> there's no extra clutter.
>
> One more thing, only vaguely on-topic: the base64_decode/_encode functions
> don't let you specify whether you want "base64" or the variant "base64url",
> they always use the former. You can use a regular expression or strtr() to
> convert the input/output, of course, but it would be more efficient (and
> perhaps for security purposes, less likely to allow timing attacks?) if
> there was built-in support. So, should we add a parameter to these
> functions to specify if the base64url variant is to be used?
>
> Thanks for your proposal!
>
> --
> Andrea Faulds
> https://ajf.me/
>
> --
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>

​Hi Andrea,

​The performance impact should be negligible; ircmaxell found a difference
of 5 microseconds.

Re: Base64url, that was another question I'd been pondering. My PoC, based
on the work of Sc00bz, covers all of RFC 4648. That includes base32hex and
base64urlsafe. Do we want to cover those as well? I've noticed a lot of
projects using a url-safe variant, so there may be popular demand for it.

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com/>​

Stas Malyshev

10 years ago

Hi!

> PHP already offers bin2hex()/hex2bin() and base64_encode()/base64_decode().
> This covers part, but not all, of RFC 4648.
>
> I'd like to extend the coverage to include, at minimum, Base32.

What's the use case for it? Is anybody using base32 now?

> I'd also like to make these functions to be written to resist cache-timing
> attacks (i.e. when used to encode/decode encryption keys for long-term
> storage). Userland PoC: https://github.com/paragonie/constant_time_encoding
> These modifications can either be made in-place (at a negligble cost on the
> scale of nanoseconds) or they can be an alternative implementation. i.e.

What modification needs to be done for existing one? Since encoding
functions (unlike comparison ones) have to process every bit anyway, so
what are timing differences for e.g. base64? Is there any existing
research for this?

>
>     * bin2hex_ts()
>     * base64_encode_ts()
>     * base32_encode_ts()

If you have encode functions, you should have decode too? Otherwise,
you'd have the same issue every time the key is read.

--
Stas Malyshev
smalyshev@gmail.com

Sascha Schumann

10 years ago

> > PHP already offers bin2hex()/hex2bin() and base64_encode()/base64_decode().
> > This covers part, but not all, of RFC 4648.
> >
> > I'd like to extend the coverage to include, at minimum, Base32.
>
> What's the use case for it? Is anybody using base32 now?

I'd have a few times if the functionality had been easily available.

Please make this a single call:

str_convert_base($in, $old_base, $new_base);

"str_" because it applies in most cases to stuff not representable as a PHP
float/int.

> > I'd also like to make these functions to be written to resist cache-timing
> > attacks (i.e. when used to encode/decode encryption keys for long-term

As this requires slowing things down, this should be an extra, optional feature.
Either to the relevant functions, or more likely globally, as it does not make
much sense on a per-function level.

Sascha

Scott Arciszewski

10 years ago

On Sat, Mar 26, 2016 at 9:55 PM, Sascha Schumann <
sascha.schumann@myrasecurity.com> wrote:

> > > PHP already offers bin2hex()/hex2bin() and
> base64_encode()/base64_decode().
> > > This covers part, but not all, of RFC 4648.
> > >
> > > I'd like to extend the coverage to include, at minimum, Base32.
> >
> > What's the use case for it? Is anybody using base32 now?
>
> I'd have a few times if the functionality had been easily available.
> ​​
>
> Please make this a single call:
>
> str_convert_base($in, $old_base, $new_base);
>
> "str_" because it applies in most cases to stuff not representable as a PHP
> float/int.
>
> > > I'd also like to make these functions to be written to resist
> cache-timing
> > > attacks (i.e. when used to encode/decode encryption keys for long-term
> ​​
>
> As this requires slowing things down, this should be an extra, optional
> feature.
> Either to the relevant functions, or more likely globally, as it does not
> make
> much sense on a per-function level.
>
> Sascha
>

​Hi Sascha,
​

Please make this a single call:

> str_convert_base($in, $old_base, $new_base);
> "str_" because it applies in most cases to stuff not representable as a PHP
> float/int.

T​hat would be ill-advised. What I'm proposing is to cover RFC 4648.

https://tools.ietf.org/html/rfc4648

These are specific base-{2^n} encoding schemes that are easy to implement
in constant time. An arbitrary change-of-base function just _begs_ people
to port Base62 or Base58 which is much more difficult to reason about when
it comes to timing safety.

Also: We already have base_convert(). If you'd like to write a wholly
separate RFC to make a function cover bases > 36, that might be useful.

I'm specifically focusing on the "let's prevent cache-timing leaks when
people encode-then-store/load-then-decode cryptographic secrets in PHP"
problem here.
​

As this requires slowing things down, this should be an extra, optional

> feature.
> Either to the relevant functions, or more likely globally, as it does not
> make
> much sense on a per-function level.

That's something to consider, but please keep in mind a sense of
perspective: Anthony measured a _negligible_ performance hit (5 * 10^-6
seconds).

Are there any real-world applications that would suffer tremendously from
this academic slow-down?

If so, we should discuss how to proceed.

If not, we might want to consider disregarding the penalty entirely.

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com/>

Sascha Schumann

10 years ago

> That's something to consider, but please keep in mind a sense of
> perspective: Anthony measured a _negligible_ performance hit (5 * 10^-6
> seconds).
>
> Are there any real-world applications that would suffer tremendously from
> this academic slow-down?

Yes, but that is a micro-benchmark.  Real applications will
have much bigger issues completely unrelated to this.  While
I can fully appreciate this topic in the context of e.g.
openssl, nobody around here has designed the current
implementation for the requirement you are after.

That does not mean it is not worth pursuing.  But the problem
might need to be reframed.

Sascha

Scott Arciszewski

10 years ago

On Sat, Mar 26, 2016 at 9:38 PM, Stanislav Malyshev <smalyshev@gmail.com>
wrote:

> Hi!
>
> > PHP already offers bin2hex()/hex2bin() and
> base64_encode()/base64_decode().
> > This covers part, but not all, of RFC 4648.
> >
> > I'd like to extend the coverage to include, at minimum, Base32.
>
> What's the use case for it? Is anybody using base32 now?
>
> > I'd also like to make these functions to be written to resist
> cache-timing
> > attacks (i.e. when used to encode/decode encryption keys for long-term
> > storage). Userland PoC:
> https://github.com/paragonie/constant_time_encoding
> > These modifications can either be made in-place (at a negligble cost on
> the
> > scale of nanoseconds) or they can be an alternative implementation. i.e.
>
> What modification needs to be done for existing one? Since encoding
> functions (unlike comparison ones) have to process every bit anyway, so
> what are timing differences for e.g. base64? Is there any existing
> research for this?
>
> >
> >     * bin2hex_ts()
> >     * base64_encode_ts()
> >     * base32_encode_ts()
>
> If you have encode functions, you should have decode too? Otherwise,
> you'd have the same issue every time the key is read.
>
> --
> Stas Malyshev
> smalyshev@gmail.com
>

​Google Authenticator and Tor Hidden Services both use base32. I was also
going to cover the decoding functions in the RFC.​

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com/>​