On Monday, 31 August 2020 at 07:49:24 UTC, Cym13 wrote:
> I obviously can't solve that conundrum on my own and there are far too many projects impacted for me to take the time and reach them all, so I've written an article showing how to predict Phobos UUIDs in practice. I hope this shows that this is a very practical and important issue that must be dealt with, and the best way for that would be to generate cryptographically secure UUIDs in Phobos.
>
> https://breakpoint.purrfect.fr/article/cracking_phobos_uuid.html
>
> tl;dr: At the moment predicting a future UUID takes only a few thousand requests. It's nothing when it comes to things like trying session cookies or password recovery tokens. If you are a project manager, check whether you use randomUUID to generate secrets and replace it by cryptographically secure UUID.

Thanks for highlighting the issue.  One query about your article -- you state:

> Phobos' randomUUID() follows these lines perfectly, using non-secure randomness.

... but actually, the code example you posted doesn't inherently use non-secure randomness: it accepts any uniform RNG.  It's therefore the user's choice whether or not to provide an RNG that is cryptographically secure or not.

This by itself seems in line with the RFC as you describe it:

> Note that the RFC does not require the use of cryptographically
> secure random numbers, but it does warn against using UUIDs for
> sensitive values if normal randomness is used.

In other words, the code as written (and as posted in your article) gives the user the choice about what their requirements are.

There is however an issue about the overload that does not take an RNG as input, which defaults to using `rndGen` (the default RNG, which on most platforms is indeed the Mersenne Twister).

So it feels like fixing the issue is not about the implementation posted in your article, but about what RNG is used by default if the parameterless overload of `randomUUID` is called.

Or have I missed something?

A related issue is whether Phobos provides _any_ cryptographically secure RNG, whether of its own implementation or by access to some other API.

On Wednesday, 2 September 2020 at 11:14:43 UTC, Kagamin wrote:
> On Monday, 31 August 2020 at 14:14:12 UTC, Cym13 wrote:
>> [1] https://docs.python.org/3/library/secrets.html
>
> or https://ruby-doc.org/stdlib-2.7.1/libdoc/securerandom/rdoc/SecureRandom.html
> But then how do you know that session ids are secrets and not just ids?

In almost all implementations, when a session ID is used it is the information that identifies the user as logged in using a given account. That information is typically sufficient to obtain access to said account, so session IDs are typically secret. Of course you can imagine or find a counter-example, but it doesn't weaken the point: randomUUID is not suitable to generate secrets.

On Wednesday, 2 September 2020 at 16:49:30 UTC, Joseph Rushton Wakeling wrote:
> Thanks for highlighting the issue.  One query about your article -- you state:
>
>> Phobos' randomUUID() follows these lines perfectly, using non-secure randomness.
>
> ... but actually, the code example you posted doesn't inherently use non-secure randomness: it accepts any uniform RNG.  It's therefore the user's choice whether or not to provide an RNG that is cryptographically secure or not.

Yes, you can provide it manually with a random number generator that is cryptographically secure. I've never seen that, not even once. All usage I've seen without exception just calls randomUUID() which uses the default PRNG which is the one attacked.

It is always possible to opt-into security, but security doesn't work if it's not by default as shown in multiple cases of projects that had vulnerable code.


> This by itself seems in line with the RFC as you describe it:
>
>> Note that the RFC does not require the use of cryptographically
>> secure random numbers, but it does warn against using UUIDs for
>> sensitive values if normal randomness is used.
>
> In other words, the code as written (and as posted in your article) gives the user the choice about what their requirements are.

Indeed, as I said the code is perfectly in line with the RFC. The issue is that the RFC predates usage, and isn't in line with said usage. Nowadays people expect UUIDs to be cryptographically secure, whether that's a fair assumption to make or not. While I could see an argument to put the blame on developers, it would not be a pragmatic one: there will always be new people coming in and falling into the same pitfall. Avoiding that pitfall entirely is possible and not too hard, therefore I personnaly recommend fixing it rather than just shifting the blame onto developers even though I think there is some truth to that.

Security only works if it is by default.

> There is however an issue about the overload that does not take an RNG as input, which defaults to using `rndGen` (the default RNG, which on most platforms is indeed the Mersenne Twister).
>
> So it feels like fixing the issue is not about the implementation posted in your article, but about what RNG is used by default if the parameterless overload of `randomUUID` is called.
>
> Or have I missed something?

You have not missed anything. Of course randomUUID itself just takes whatever the RNG provides. The point of the article was however centered arround randomUUID because while attacking RNGs directly is fairly common, I had received doubts that this could be attacked in practice in the context of UUIDs. I wanted to prove that, yes, even though the attack is harder, it is possible to attack a bad PRNG in this context.

> A related issue is whether Phobos provides _any_ cryptographically secure RNG, whether of its own implementation or by access to some other API.

Indeed, it is the heart of the issue. I think quite strongly that Phobos must provide access to the system's CSPRNG.

On Thursday, 3 September 2020 at 13:23:39 UTC, Cym13 wrote:
> On Wednesday, 2 September 2020 at 16:49:30 UTC, Joseph Rushton Wakeling wrote:
>> ...

I feel that answer was confused, let me reformulate.

You are correct when you say that randomUUID() alone just takes whatever the RNG provides and isn't broken by itself. Should you provide cryptographically secure randomness it would be OK to use. However I have never seen randomUUID() used with a PRNG other than the default one (and I searched), which is what I attacked in that article. The reason why I focus on UUID generation and not just breaking the default PRNG on its own is twofold: first I saw much more bad usage of randomUUID() than of uniform() itself, and second some people had expressed doubts that it was exploitable at all in this context. My main goal with this article is not to change randomUUID itself (as you pointed out, it does not present any bug), but to change the default PRNG used for randomUUID() to be a cryptographically secure one because this is the only way to prevent more people to fall into the same trap of expecting it to be secure.

Am Thu, 03 Sep 2020 13:31:01 +0000 schrieb Cym13:

> On Thursday, 3 September 2020 at 13:23:39 UTC, Cym13 wrote:
>> On Wednesday, 2 September 2020 at 16:49:30 UTC, Joseph Rushton Wakeling wrote:
>>> ...
> 
> I feel that answer was confused, let me reformulate.
> 
> You are correct when you say that randomUUID() alone just takes whatever the RNG provides and isn't broken by itself. Should you provide cryptographically secure randomness it would be OK to use. However I have never seen randomUUID() used with a PRNG other than the default one (and I searched), which is what I attacked in that article. The reason why I focus on UUID generation and not just breaking the default PRNG on its own is twofold: first I saw much more bad usage of randomUUID() than of uniform() itself, and second some people had expressed doubts that it was exploitable at all in this context. My main goal with this article is not to change randomUUID itself (as you pointed out, it does not present any bug), but to change the default PRNG used for randomUUID() to be a cryptographically secure one because this is the only way to prevent more people to fall into the same trap of expecting it to be secure.

As the "original author" of that module I can probably add some background information on this issue:

The UUID module is mostly a 1:1 port from boost.uuid. I don't remember exactly which boost version was used and whether it included a function which used the library default random number generator. Current docs in boost however also use mt19937 without explicitly warning the user this is not cryptographically secure: https://www.boost.org/doc/libs/1_62_0/ libs/uuid/uuid.html#boost/uuid/random_generator.hpp

So this is where the problem originally came from, although it might have been my mistake to provide a default overload using the system RNG.


Unfortunately, we can not silently replace this overload to use a secure RNG: On linux, would we use random or urandom? And the system rng can block on low entropy, which could cause regressions in some applications. Also some applications (like vibe.d) would probably rather block a fiber than a thread, which complicates things more.


I propose the following:
1) Deprecate the version using the system RNG. Add a hint in the message
that this function is not cryptographicallly secure. Add a reference to
documentation how to update code.
2) Update documentation examples to show how to provide the phobos
default RNG. State that this is not cryptographically secure.
3) Optionally: Implement a Secure, System based RNG.

I'll open a pull request for steps 1-2 today, so that the immediate problem is solved. I'll also have a look how difficult it is to do 3).


-- 
Johannes

On Saturday, 5 September 2020 at 10:41:34 UTC, Johannes Pfau wrote:
> Unfortunately, we can not silently replace this overload to use a secure RNG: On linux, would we use random or urandom? And the system rng can block on low entropy, which could cause regressions in some applications. Also some applications (like vibe.d) would probably rather block a fiber than a thread, which complicates things more.

On linux, you would use /dev/urandom (or getrandom(2) if you don't need to support old kernel versions), since it is just as secure as /dev/random and does not block. [1]

[1] https://www.2uo.de/myths-about-urandom/

Am Sat, 05 Sep 2020 13:06:14 +0000 schrieb Paul Backus:

> On Saturday, 5 September 2020 at 10:41:34 UTC, Johannes Pfau wrote:
>> Unfortunately, we can not silently replace this overload to use a secure RNG: On linux, would we use random or urandom? And the system rng can block on low entropy, which could cause regressions in some applications. Also some applications (like vibe.d) would probably rather block a fiber than a thread, which complicates things more.
> 
> On linux, you would use /dev/urandom (or getrandom(2) if you don't need
> to support old kernel versions), since it is just as secure as
> /dev/random and does not block. [1]
> 
> [1] https://www.2uo.de/myths-about-urandom/

Hmm, good to know, thanks. Seems kinda stupid that urandom returns insecure data before it is first seeded at boot though, but I guess that's the way it is...

-- 
Johannes

On Saturday, 5 September 2020 at 10:41:34 UTC, Johannes Pfau wrote:
>
> 3) Optionally: Implement a Secure, System based RNG.
>
> I'll open a pull request for steps 1-2 today, so that the immediate problem is solved. I'll also have a look how difficult it is to do 3).

Have a look at these two well-tested implementations:

https://github.com/libmir/mir-random/blob/master/source/mir/random/engine/package.d
https://github.com/vibe-d/vibe.d/blob/master/crypto/vibe/crypto/cryptorand.d

You could even copy-paste one of them into Phobos as Vibe.d's implementation is based on Mir's which in turn is Boost-licensed.

On Monday, 31 August 2020 at 16:10:33 UTC, Steven Schveighoffer wrote:
> On 8/31/20 9:17 AM, WebFreak001 wrote:
>> On Monday, 31 August 2020 at 07:49:24 UTC, Cym13 wrote:
>>> Hi there,
>>>
>>> As always when I make an appearance it's that something has gone wrong. Either in a popular library or D itself... This time it's a little bit of both.
>>>
>>> [...]
>> 
>> Thanks for the post! Read the crypto review before and surely enough this time again it was really fun to read through the whole post. I also love the random pictures in your posts :p
>
> I share this sentiment, great article!
>
>> 
>> I'm not too sure if I ever use randomUUID now, but if it was used in vibe.d applications by default that's terrifying to me.
>
> I had to look it up to make sure. The session id producer uses what is recommended in the article:
>
> https://github.com/vibe-d/vibe.d/blob/master/crypto/vibe/crypto/cryptorand.d#L125
>
> whew!
>
> -Steve

I'm trying to create a crypto random number generator based on extracting only what is essential from the above code, and the only thing blocking this effort are two compile errors : both related to 'undefines' for 'IOMode' and @blocking
i.e.

gdc -o aexe rand_crypto.d
rand_crypto.d:62:12: error: undefined identifier ‘IOMode’
     size_t read(scope ubyte[] dst, IOMode mode) @blocking;
            ^
rand_crypto.d:77:21: error: undefined identifier ‘IOMode’
     override size_t read(scope ubyte[] dst, IOMode mode) @safe;
                     ^
rand_crypto.d:29:29: error: undefined identifier ‘blocking’
     @property bool empty() @blocking;

After numerous searches, I'm unable to get a definition of vibe 'IOMode'
.. and haven't a clue on @blocking is about... Any help is greatly appreciated.

On 9/5/20 6:41 AM, Johannes Pfau wrote:
> 
> Unfortunately, we can not silently replace this overload to use a secure
> RNG: On linux, would we use random or urandom? And the system rng can
> block on low entropy, which could cause regressions in some applications.
> Also some applications (like vibe.d) would probably rather block a fiber
> than a thread, which complicates things more.

1. The default should be changed, even if it's not as performant. There is no promise about randomUUID's performance.

2. vibe.d does not depend on this, so there are no worries about blocking a thread.

-Steve