-3

Is there an exploit for this bug for python's sort implementation?

http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/

closed as off-topic by schroeder, Xander, Bob Brown, RoraΖ, Eric G Feb 26 '15 at 21:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking us to break the security of a specific system for you are off-topic unless they demonstrate an understanding of the concepts involved and clearly identify a specific problem." – schroeder, Xander, Bob Brown, Eric G
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    Is there a security vulnerability? Just because it is a bug does not mean that there is a vulnerability. – schroeder Feb 26 '15 at 18:09
  • @schroeder it could lead at least to crash due to unhandled exception or segfault. – Smit Johnth Feb 26 '15 at 19:14
  • "could" being the operative term. The real question is: "Is there a vulnerability with this bug?" – schroeder Feb 26 '15 at 19:52
  • @schroeder That's what i'm asking. Now open the question. – Smit Johnth Feb 27 '15 at 6:18
  • Then this is a programming question, not an InfoSec question, yet. As there does not seem to be a CVE registered for this, it appears as though there isn't a vulnerability, but the investigation of the code for possible vulnerabilities is outside the scope of this site. – schroeder Feb 27 '15 at 7:15
2

That version also contains the bug and was intended to work for arrays with up to 2^64 elements. However, on current machines it is not possible to trigger an out-of-bounds error in the Python version: it allocates 85 elements for runLen, which suffices (following our analysis in the full paper) for arrays with less than 2^49 elements. For comparison, the current most powerful supercomputer http://en.wikipedia.org/wiki/Tianhe-2 has about 2^50 bytes of memory in total.

It is not currently possible to trigger the bug in CPython, since it requires a data set that does not fit in today's machines. Since the bug cannot be triggered, in cannot be exploited.

As the article mentions, some Java implementations of this algorithm use smaller arrays which can overflow with smaller datasets (a few hundred MB in the sample code, if I read it correctly). Since this is a buffer overflow, there is a fair chance that it is exploitable.

  • I think the java implementation simply crashes since java validates array indices. So it certainly doesn't lead to RCE by default. It might overwrite some unrelated data in the same array, but does limited damage with typical usage. – CodesInChaos Feb 26 '15 at 19:45
  • @CodesInChaos DoS is still a security issue. – Smit Johnth Feb 27 '15 at 6:20
  • Bugs that cause crashes in itself isn't necessarily a DoS issue. – schroeder Feb 27 '15 at 7:19
  • @schroeder but they may be too. – Smit Johnth Feb 27 '15 at 16:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.