Switching SecureTokens to Base58

[robertomiranda]

ref #18217 (comment)

[robertomiranda]

cc @dhh, @chancancode

[dhh]

Looks good to me, but I'll let someone in the know actually review the algorithm ;).

[vipulnsward]

Should be examples of base62

[vipulnsward]

puts is not needed

[matthewd]

An actual base62 encoder seems needlessly complicated for our purposes... see my comments on previous discussion.

[robertomiranda]

whats's of issue with use base64 instead of base62?

[matthewd]

@robertomiranda it contains characters we don't want. That was also discussed to death in the previous PR.

[dhh]

@matthewd What are you suggesting as an alternative here?

[matthewd]

Something like:

random_bytes(chars).unpack("C*").map do |byte|
  idx = byte % 64
  idx = random_number(62) if idx >= 62
  BASE62_CHARS[idx]
end.join

And having looked closer, I've just realised that @robertomiranda's implementation is actually Wrong: it's not generating a uniformly random string.

[georgeclaghorn]

The argument is named bytes, not n.

[matthewd]

The above is obviously assuming that random_bytes is faster / otherwise betterer than a series of calls to random_number... otherwise, life gets much simpler:

''.tap do |string|
  length.times { string << BASE62_CHARS[random_number(62)] }
end

[egilburg]

it's not generating a uniformly random string.

idx = random_number(62) if idx >= 62 is not uniform either (it'll produce a slight bias towards integers than towards letters). But is the goal here to produce a cryptographically secure random string, or something "close enough"?

Also consider readability for those who may want to write these strings down - some existing algorithms, for exampe, avoid uppercase I (i) as it looks like lowercase l (L), same with o/O/0.

[chancancode]

Also consider readability for those who may want to write these strings down - some existing algorithms, for exampe, avoid uppercase I (i) as it looks like lowercase l (L), same with o/O/0.

Assuming a uniform distribution, with Base58 at 24 characters we are still getting 140 random bits, which is still miles better than a random UUID, so I guess why not. It's useful for things like "write down these TFA lock out code in case you lost your phone", or "enter this manually if your phone can't scan this QR code" scenario.

But is the goal here to produce a cryptographically secure random string, or something "close enough"?

IMO, "close enough" is a dangerous territory here. Once you are off the tracks, all bets are off and it's difficult to tell what you are up against (e.g. Is this still equivalent or better than a random UUID? How would we prove it?). It also makes it difficult to put any guarantee on it hence recommend using this API for any specific purpose.

[dhh]

👍 on what Godfrey said.

On Jan 5, 2015, at 11:46, Godfrey Chan notifications@github.com wrote:

Also consider readability for those who may want to write these strings down - some existing algorithms, for exampe, avoid uppercase I (i) as it looks like lowercase l (L), same with o/O/0.

Assuming a uniform distribution, with Base58 at 24 characters we are still getting 140 random bits, which is still miles better than a random UUID, so I guess why not. It's useful for things like "write down these TFA lock out code in case you lost your phone", or "enter this manually if your phone can't scan this QR code" scenario.

But is the goal here to produce a cryptographically secure random string, or something "close enough"?

IMO, "close enough" is a dangerous territory here. Once you are off the tracks, all bets are off and it's difficult to tell what you are up against (e.g. Is this still equivalent or better than a random UUID? How would we prove it?). It also makes it difficult to put any guarantee on it hence recommend using this API for any specific purpose.

—
Reply to this email directly or view it on GitHub.

[matthewd]

@egilburg I'm obviously being thick, because that looks uniform to me. Care to expand?

[egilburg]

@matthewd perhaps I'm the thicker one here, but this is a bit confusing to me:

  idx = byte % 64
  idx = random_number(62) if idx >= 62

It seems you get one of 64 variations, but 2 of those are "bad" so you "reroll" them to a backup implementation. Why would just idx = random_number(62) not work then?

[matthewd]

256 values in a byte; % 64 is safe (drops two bits), % 62 would bias.

I did offer a vastly simpler alternative that just uses random_number from the outset... this version was building on an (untested) assumption that doing most of the work with a single call to random_bytes might be noticeably more efficient.