Pages

August 22, 2012

Not So Random Numbers. Take Two

George Argyros and Aggelos Kiayias have published recently an awesome research concerning attacks on pseudo random generator in PHP. However, it lacked practical tools implementing this attack. That is why we conducted our own research which led to the creation of a program to perform the bruteforce of PHPSESSID.

How can we get mt_rand seed via PHPSESSID?


PHPSESSID is generated this way:

md5( client IP . timestamp . microseconds1 . php_combined_lcg() )
  • client IP is known to the attacker;
  • timestamp is known through Date HTTP-header;
  • microseconds1 – a value from 0 to 1000000;
  • php_combined_lcg() – an example value is 0.12345678.

To generate php_combined_lcg(), two seeds are used:

S1 = timestamp XOR (microseconds2 << 11)
S2 = pid XOR (microseconds3 << 11)
  • timestamp is the same;
  • microseconds2 is greater than microseconds1 (when the first time measurement was made) by 0–3;
  • pid is the id of the current process (0–32768, 1024–32768 on Unix);
  • microseconds3 is greater than microseconds2 by 1–4.

The greatest entropy is contained in microseconds1, however with the use of two techniques it can be substantially reduced.

Adversarial Time Synchronization


The technique is aimed at sending pairs of requests so that to determine the moment when the second in the Date HTTP header changes.

HTTP/1.1 200 OK
Date: Wed, 08 Aug 2012 06:05:14 GMT

HTTP/1.1 200 OK
Date: Wed, 08 Aug 2012 06:05:15 GMT

If it happened, the microseconds between our requests zeroed. By sending requests with dynamic delays it is possible to synchronize local value of microseconds with the server one.

Request Twins


The principle of this technique is simple. The attacker needs to send two requests: the first one — to reset their own password and the second one — to reset that of an administrator. The gap between microseconds will be minimal.

To sum up, an MD5 PHPSESSID hash is bruteforced for microseconds, the deltas of subsequent time measurements, and pid. As for pid, the authors have not mentioned such a great helper as Apache server-status which reveals among other information the pids of the processes which serve the requests.

To realize the bruteforce, a module for the popular program PasswordsPro has been initially created. However, this solution made it impossible to take into account the positive linear correlation between deltas of microseconds, so it bruteforced the full range of values. The speed was about 12 million hashes per second.

That is why we created our own GUI application for this task.


The speed is about 16 million hashes per second, seed calculation takes less than an hour on 3.2 GHz Quad Core i5.

Having pid and php_combined_lcg one can compute the seed used in mt_rand. It is generated this way:

(timestamp x pid) XOR (106 x php_combined_lcg())

Besides, php_combined_lcg is used as additional entropy for the uniqid function (if it is called with the second argument being true).

So, if a web application uses standard PHP sessions, it is possible to obtain the random numbers generated via mt_rand(), rand(), and uniqid().

How can we get mt_rand seed through one of the random numbers leakage?

The seed used for mt_rand is an unsigned integer 2^32. If a random number leaked, it is possible to get the seed using PHP itself and rainbow tables. It takes less than 10 minutes.
The scripts to generate rainbow tables, search the seed, and ready-made tables are available here: http://www.gat3way.eu/poc/mtrt/


What to look for in the code?

All the mt_rand(), rand(), uniqid(), shuffle(), lcg_value(), etc. The only secure function is openssl_random_pseudo_bytes(), but it is rarely used in web applications. The main ways of defense against such attacks are the following:

  • MySQL function RAND() — it can be also predicted though.
  • Suhosin patch — does not patch mt_srand, srand. The Suhosin extension should also be installed.
  • /dev/urandom — the securest way.



Arseny Reutov
Timur Yunusov
Dmitry Nagibin

138 comments:

  1. FUCKING AWESOME!!! I was thinking of writing my own tools, but i see you guys were way ahead of me and already did it!!! You rock!:)

    ReplyDelete
  2. wait, aren't your tools available for download?

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. This comment has been removed by a blog administrator.

      Delete
  3. you guys really rock, honestly. I don't think i could have finished this by myself. my math skills area a little rusty:)

    ReplyDelete
  4. Is this applicable to session_id() too?

    ReplyDelete
  5. it should be noted that you can add additional entropy through session.entropy_length and session.entropy_file and since 5.4.0 /dev/urandom or /dev/arandom is used if available by default.

    ReplyDelete
    Replies
    1. Yes, these php.ini directives eliminate the possibility of PHPSESSID bruteforce.

      Delete
  6. can you give more details on the ATS technique? Thanks.

    ReplyDelete
    Replies
    1. 1. connect to a web server and send request pairs: the first one to a non-existent page so that it will take a minimum time for the web-server to return the response, and the second one to our target web-application
      2. get an average time interval between sending an HTTP request and receiving the response (= RTT)
      3. when the seconds in Date HTTP-header of the two requests changed we begin to approximate the time of remote microseconds in local time using RTTs of the two requests divided by two and offsetting the delay between requests
      4. additionally if session_start() is called somewhere deeper in the code, you may try to install the web-app locally and get the approximate time when it is called.

      Delete
  7. Chemistry Cat? Please, know your meme http://knowyourmeme.com/memes/chemistry-cat
    I Would use the "Get all the random numbers" or something like that.

    Apart from that, this is a great article.

    ReplyDelete
    Replies
    1. Thanks! And yes, my meme is bad, and I should feel bad.

      Delete
  8. Anybody still using MD5? You can simply use functions like e.g. sha512 for generating session IDs:

    http://php.net/manual/en/session.configuration.php#ini.session.hash-function

    ReplyDelete
  9. can you write something on MySQL function RAND() ?
    also for your deltas why haven't you used ranges as you said at the start of the article?:)

    ReplyDelete
  10. Hi guys, can you please provide also source code for the PHPSESSID bruteforcer? My app initializes lcg before session_start() is called, so I'd need to tweak the parameters a little bit.
    Thanks

    ReplyDelete
    Replies
    1. Hi!
      I am not sure how this is possible because PHP does not expose LCG seeding function to users. Does your app use lcg_value() or uniqid($more_entropy = true) before session_start()?

      Delete
  11. Amazing article, but the graphics which you have used developed more exciting to analyse & visualize your thought, looking forward to view more…

    http://www.marsleisure.com

    ReplyDelete
  12. Awesome content, but the pictures which you have used made more interesting to study, awaiting to view more…
    http://www.gardendecors.net

    ReplyDelete
  13. This comment has been removed by a blog administrator.

    ReplyDelete
  14. This comment has been removed by a blog administrator.

    ReplyDelete
  15. This comment has been removed by a blog administrator.

    ReplyDelete
  16. This comment has been removed by a blog administrator.

    ReplyDelete
  17. This comment has been removed by a blog administrator.

    ReplyDelete
  18. This comment has been removed by a blog administrator.

    ReplyDelete
  19. This comment has been removed by a blog administrator.

    ReplyDelete
  20. This comment has been removed by a blog administrator.

    ReplyDelete
  21. This comment has been removed by a blog administrator.

    ReplyDelete
  22. This comment has been removed by a blog administrator.

    ReplyDelete
  23. This comment has been removed by a blog administrator.

    ReplyDelete
  24. This comment has been removed by a blog administrator.

    ReplyDelete
  25. This comment has been removed by a blog administrator.

    ReplyDelete
  26. This comment has been removed by a blog administrator.

    ReplyDelete
  27. This comment has been removed by a blog administrator.

    ReplyDelete
  28. This comment has been removed by a blog administrator.

    ReplyDelete
  29. This comment has been removed by a blog administrator.

    ReplyDelete
  30. This comment has been removed by a blog administrator.

    ReplyDelete
  31. This comment has been removed by a blog administrator.

    ReplyDelete
  32. This comment has been removed by a blog administrator.

    ReplyDelete
  33. This comment has been removed by a blog administrator.

    ReplyDelete
  34. This comment has been removed by a blog administrator.

    ReplyDelete
  35. This comment has been removed by a blog administrator.

    ReplyDelete
  36. This comment has been removed by a blog administrator.

    ReplyDelete
  37. This comment has been removed by a blog administrator.

    ReplyDelete
  38. This comment has been removed by a blog administrator.

    ReplyDelete
    Replies
    1. This comment has been removed by a blog administrator.

      Delete
  39. This comment has been removed by a blog administrator.

    ReplyDelete
  40. This comment has been removed by a blog administrator.

    ReplyDelete
  41. This comment has been removed by a blog administrator.

    ReplyDelete
  42. This comment has been removed by a blog administrator.

    ReplyDelete
  43. This comment has been removed by a blog administrator.

    ReplyDelete
  44. This comment has been removed by a blog administrator.

    ReplyDelete
  45. This comment has been removed by a blog administrator.

    ReplyDelete
  46. This comment has been removed by a blog administrator.

    ReplyDelete
  47. This comment has been removed by a blog administrator.

    ReplyDelete
  48. This comment has been removed by a blog administrator.

    ReplyDelete
  49. This comment has been removed by a blog administrator.

    ReplyDelete
  50. This comment has been removed by a blog administrator.

    ReplyDelete
  51. This comment has been removed by a blog administrator.

    ReplyDelete
  52. This comment has been removed by a blog administrator.

    ReplyDelete
  53. This comment has been removed by a blog administrator.

    ReplyDelete
  54. This comment has been removed by a blog administrator.

    ReplyDelete
  55. This comment has been removed by a blog administrator.

    ReplyDelete
  56. This comment has been removed by a blog administrator.

    ReplyDelete
  57. This comment has been removed by a blog administrator.

    ReplyDelete
  58. This comment has been removed by a blog administrator.

    ReplyDelete
  59. This comment has been removed by a blog administrator.

    ReplyDelete
  60. This comment has been removed by a blog administrator.

    ReplyDelete
  61. This comment has been removed by a blog administrator.

    ReplyDelete
  62. This comment has been removed by a blog administrator.

    ReplyDelete
  63. This comment has been removed by a blog administrator.

    ReplyDelete
  64. This comment has been removed by a blog administrator.

    ReplyDelete
  65. This comment has been removed by a blog administrator.

    ReplyDelete
  66. This comment has been removed by a blog administrator.

    ReplyDelete
  67. This comment has been removed by a blog administrator.

    ReplyDelete
  68. This comment has been removed by a blog administrator.

    ReplyDelete
  69. This comment has been removed by a blog administrator.

    ReplyDelete
  70. This comment has been removed by a blog administrator.

    ReplyDelete
  71. This comment has been removed by a blog administrator.

    ReplyDelete
  72. This comment has been removed by a blog administrator.

    ReplyDelete
  73. This comment has been removed by a blog administrator.

    ReplyDelete
  74. This comment has been removed by a blog administrator.

    ReplyDelete
  75. This comment has been removed by a blog administrator.

    ReplyDelete
  76. This comment has been removed by a blog administrator.

    ReplyDelete
  77. This comment has been removed by a blog administrator.

    ReplyDelete
  78. This comment has been removed by a blog administrator.

    ReplyDelete
  79. This comment has been removed by a blog administrator.

    ReplyDelete
  80. This comment has been removed by a blog administrator.

    ReplyDelete
  81. This comment has been removed by a blog administrator.

    ReplyDelete
  82. This comment has been removed by a blog administrator.

    ReplyDelete
  83. This comment has been removed by a blog administrator.

    ReplyDelete
  84. This comment has been removed by a blog administrator.

    ReplyDelete
  85. This comment has been removed by a blog administrator.

    ReplyDelete
  86. This comment has been removed by a blog administrator.

    ReplyDelete
  87. This comment has been removed by a blog administrator.

    ReplyDelete
  88. This comment has been removed by a blog administrator.

    ReplyDelete
  89. This comment has been removed by a blog administrator.

    ReplyDelete
  90. This comment has been removed by a blog administrator.

    ReplyDelete
  91. This comment has been removed by a blog administrator.

    ReplyDelete
  92. This comment has been removed by a blog administrator.

    ReplyDelete
  93. This comment has been removed by a blog administrator.

    ReplyDelete
  94. This comment has been removed by a blog administrator.

    ReplyDelete
  95. This comment has been removed by a blog administrator.

    ReplyDelete
  96. This comment has been removed by a blog administrator.

    ReplyDelete
  97. This comment has been removed by a blog administrator.

    ReplyDelete
  98. This comment has been removed by a blog administrator.

    ReplyDelete
  99. This comment has been removed by a blog administrator.

    ReplyDelete
  100. This comment has been removed by a blog administrator.

    ReplyDelete
  101. This comment has been removed by a blog administrator.

    ReplyDelete
  102. This comment has been removed by a blog administrator.

    ReplyDelete
  103. This comment has been removed by a blog administrator.

    ReplyDelete
  104. This comment has been removed by a blog administrator.

    ReplyDelete
  105. This comment has been removed by a blog administrator.

    ReplyDelete
  106. This comment has been removed by a blog administrator.

    ReplyDelete
  107. This comment has been removed by a blog administrator.

    ReplyDelete
  108. This comment has been removed by a blog administrator.

    ReplyDelete
  109. This comment has been removed by a blog administrator.

    ReplyDelete
  110. This comment has been removed by a blog administrator.

    ReplyDelete
  111. This comment has been removed by a blog administrator.

    ReplyDelete
    Replies
    1. This comment has been removed by a blog administrator.

      Delete
  112. This comment has been removed by a blog administrator.

    ReplyDelete
  113. This comment has been removed by a blog administrator.

    ReplyDelete
  114. This comment has been removed by a blog administrator.

    ReplyDelete
  115. This comment has been removed by a blog administrator.

    ReplyDelete
  116. This comment has been removed by a blog administrator.

    ReplyDelete
  117. This comment has been removed by a blog administrator.

    ReplyDelete
  118. This comment has been removed by a blog administrator.

    ReplyDelete
  119. This comment has been removed by a blog administrator.

    ReplyDelete
  120. This comment has been removed by a blog administrator.

    ReplyDelete
  121. This comment has been removed by a blog administrator.

    ReplyDelete