CVE-2020-10735とその「修正」

2022年9月7日にPythonのセキュリティアップデートがリリースされました。

「修正」された脆弱性はCVE-2020-10735です。ざっくりと言うと、Pythonで使われている整数・文字列間変換アルゴリズムがあまりイケてなく¹、たとえば10進法で10万桁の文字列を整数に変換すると50ミリ秒、100万桁の場合は5秒もかかってしまうということが起こるので²、DoS攻撃に使えてしまうというものでした。

ここで、Python開発チームのとった対処法はアルゴリズムの改良ではなく³、大きな整数と文字列を変換しようとするとエラーになるような「修正」です。

>>> n = 10**4300
>>> str(n)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: Exceeds the limit (4300) for integer string conversion

デフォルトでは、文字列にして4300文字を超えるような整数に対してエラーとなります。上の例だと、$10^{4300}$が10進法で4301桁なので文字列に変換しようとしたときにエラーとなっています。前のバージョンでは難なく動いていたので、パッチリリースで後方互換性をぶっ壊した⁴ことなどが議論の的となっています⁵。

西暦10^4300年問題

さて、次のようなPythonプログラムを考えましょう。

import calendar

year = eval(input("year?"))
month = eval(input("month?"))
calendar.TextCalendar().prmonth(year, month)

ユーザーに年と月を入力してもらい⁶、calendarモジュールのTextCalendarクラスを使ってその年・月のカレンダーを出力しています。たとえば、

year?2022
month?9

と入力すると、2022年9月のカレンダーが標準出力に出力されます。

   September 2022
Mo Tu We Th Fr Sa Su
          1  2  3  4
 5  6  7  8  9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30

ここで、遠い未来に思いを馳せてみることにしましょう。なぜなら西暦$10^{4300}$-1年12月のカレンダーの表示だって簡単なんです、Pythonならね⁷。

year?10**4300-1
month?12

December 99999999999999999999999999999999999999999999999999999999999999999999999
... (省略) ...
9999999999999999
Mo Tu We Th Fr Sa Su
       1  2  3  4  5
 6  7  8  9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31

ところが、その次の月である$10^{4300}$年1月のカレンダーを表示させようとするとエラーになります。

year?10**4300
month?1

Traceback (most recent call last):
  File "//prog.py", line 5, in <module>
    calendar.TextCalendar().prmonth(year, month)
  File "/usr/local/lib/python3.10/calendar.py", line 352, in prmonth
    print(self.formatmonth(theyear, themonth, w, l), end='')
  File "/usr/local/lib/python3.10/calendar.py", line 360, in formatmonth
    s = self.formatmonthname(theyear, themonth, 7 * (w + 1) - 1)
  File "/usr/local/lib/python3.10/calendar.py", line 345, in formatmonthname
    s = "%s %r" % (s, theyear)
ValueError: Exceeds the limit (4300) for integer string conversion

なんということでしょう。西暦$10^{4300}$-1年までは動くけれど、西暦$10^{4300}$年になると途端に動かなくなるプログラムが書けてしまいました⁸。西暦$10^{4300}$年問題の爆誕です⁹。遠い将来、陽子崩壊¹⁰や真空崩壊¹¹など、セカイ系主人公ですら全力で逃げるレベルの、幾度もの破滅の危機を乗り越えた後の人類に降りかかるのは2022年9月に仕込まれた「バグ」なのでした¹²。子孫がんばれ。超がんばれ。

ざっくりと第0次近似でPython $\simeq$ CPythonとして説明しています。CPython以外なら、たとえばPyPyでの議論はここ。 ↩
（マシンによって違う）具体的に何秒かという数字よりも、サイズ$n$の入力に対し計算量が$O(n^2)$で増えていくのがヤバいです。 ↩
もうちょっとマシなアルゴリズムにしようよという議論はこちら。 ↩
セマンティックバージョニングによると、パッチバージョンを上げるときは後方互換性を伴ったバグ修正しかしてはいけないはず。 ↩
こことかこことかこことかこことかこことか。 ↩
ユーザー入力をサニタイズせずそのままeval()に食わせていますが、良い子は真似しないでね。 ↩
このカレンダーが合っていることは、ツェラーの公式を使うと（$y=400n-1$（$n$は整数）と書けるのでいろいろと簡単になって）すぐに分かります。 ↩
本当は、年と月を入力しなくても勝手に現在日時を取得してカレンダーを表示するプログラムにしようと思ったのですが、Python標準のdatetimeモジュールは9999年までしか扱えないのでした。恐るべし、西暦10000年問題。 ↩
西暦$10^{4300}$年問題を含めたいわゆる「Y10K and Beyond」問題についての解決策はすでにRFC 2550（和訳）として提案されており、西暦$10^{18308}$年まで例を交えながら論じられています。なお、このRFCが公開されたのは1999年4月1日です。 ↩
2022年10月現在、陽子の平均寿命の実験的下限は信頼水準90%で$3.6\times 10^{29}$年（invisible mode、ソースはこれとかこれとか）。 ↩
これによると信頼水準95%で$10^{65}$～$10^{1383}$年くらいに起きます。こちらも参照のこと。 ↩
$10^{4300}$年まで人類がPythonを使っているのか、それまでこの「バグ」が修正されないのか、内部表現の桁溢れではないので本質的な問題ではないとか、まだ西暦が使われているのか、グレゴリオ暦なのか、人類が生き延びていたとしてそれは「人類」なのか、そもそも宇宙はまだあるのかなど、異論は認める。 ↩