Rack::Session::Redis#generate_unique_sid's unique session key generation logic does not work

[hogelog]

Rack::Session::Redis#generate_unique_sid is a method that generates new unique session key that it does not conflict with an existing session key.

But it seems does not work well after #37 PR.

• Rack::Session::Redis#generate_unique_sid skip generating unique session key logic when session.empty?.
  • https://github.com/redis-store/redis-rack/blob/v2.1.4/lib/rack/session/redis.rb#L23
• But generate_unique_sid's argument session is always empty hash.
  • https://github.com/redis-store/redis-rack/blob/v2.1.4/lib/rack/session/redis.rb#L39-L40
• So Rack::Session::Redis#generate_unique_sid's unique session key generation logic does not work.

Reproduction

I checked with the following code, which is prone to session key collisions.

require "bundler/inline"

gemfile do
  source "https://rubygems.org"
  gem "sinatra", "2.2.0"
  gem "webrick", "1.7.0"
  gem "redis-rack", "2.1.4"
end

require "sinatra"
require "redis-rack"

# Returns a counted-up value for each invocation since the process was started
class Countup
  def self.hex(len)
    @count ||= 0
    @count += 1
    sprintf("%0#{len}d", @count)
  end
end

enable :sessions
set :sessions, secure_random: Countup
set :session_store, Rack::Session::Redis

get "/" do
  session[:access] ||= 0
  session[:access] += 1
  "sid: #{session.id}, access: #{session[:access]}"
end

Sinatra::Application.run!

Procedure

• Launch above application with ruby app.rb
• Access by browser (sid: 00000000000000000000000000000001)
  • session[:access] increases with each access.
• Kill ruby app.rb application and relaunch.
• Access by secret browser (sid: 00000000000000000000000000000001)
  • session[:access] is initialized.
  • session is shared with first browser and secret browser.

The above situation occurs even with correct random number generation logic, although the collisions are fewer.

How to fix

Revert #37 is easy way, maybe.
If you want to avoid that, it would require a more complicated modification.

[tubbo]

@hogelog Given one uses the default SecureRandom.hex, and doesn't circumvent the logic for actually generating a random value, how often could a session ID collision happen?

[hogelog]

@hogelog Given one uses the default SecureRandom.hex, and doesn't circumvent the logic for actually generating a random value, how often could a session ID collision happen?

Unfortunately, I don't know exactly how often ID collisions happen, as I noticed it while looking at the code.

In default, sid (= public session id) is SecureRandom.hex(32) when secure: true.
And private session id value is "2::#{Digest::SHA256.hexdigest(sid)}".
https://github.com/rack/rack-session/blob/9cc829041ba82c9c1313fdf6ca5ce446621dfd88/lib/rack/session/abstract/id.rb#L248-L250

(Assuming that SecureRandom generates perfectly uniformly)
So public session id collision rate is 1 - ((2^256 - 1)/2^256)^N. If session count is 10,000,000, rate is 1 - ((2^256 - 1)/2^256)^10,000,000 ≈ 8.6 × 10^-71.
https://www.wolframalpha.com/input?i=1+-+%28%282%5E256-1%29%2F2%5E256%29%5E10000000
Ref: https://en.wikipedia.org/wiki/Birthday_problem

SHA256 is hash function digesting to 256 bits. If SHA256 is a perfect hash function without bias, then a 256-bit input would be hashed to a 256-bit value without collision.

Ofcource there are no perfect random generator and hash function algorightms, real collision rate would be more often. But, in any case, collision rate would be not so high.

[hogelog]

On the other hand, the code at https://github.com/redis-store/redis-rack/blob/v2.1.4/lib/rack/session/redis.rb#L23 does not seem to be working properly at the moment. I am thinking of sending a fix along with tests.

[tubbo]

@hogelog i just merged your changes to redis-store, wondering if that helps any with this issue?