西暦10^4300年問題

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

2022年9月7日に[Python](https://www.python.org/)のセキュリティアップデートがリリースされました。

- [Python Insider - Python releases 3.10.7, 3.9.14, 3.8.14, and 3.7.14 are now available](https://pythoninsider.blogspot.com/2022/09/python-releases-3107-3914-3814-and-3714.html)
- [窓の杜 - 「Python」に定例外のセキュリティアップデート](https://forest.watch.impress.co.jp/docs/news/1438284.html)
- [yKesamaru @ Zenn - Python: int/str 型変換における破壊的変更のお知らせ](https://zenn.dev/ykesamaru/articles/2175b317a5410e)
 
「修正」された脆弱性は[CVE-2020-10735](https://nvd.nist.gov/vuln/detail/CVE-2020-10735)です。ざっくりと言うと、Pythonで使われている[整数・文字列間変換アルゴリズム](https://github.com/python/cpython/blob/v3.10.7/Objects/longobject.c)があまりイケてなく[^pypy]、たとえば10進法で10万桁の文字列を整数に変換すると50ミリ秒、100万桁の場合は5秒もかかってしまうということが起こるので[^quadratic]、DoS攻撃に使えてしまうというものでした。

ここで、Python開発チームのとった対処法はアルゴリズムの改良ではなく[^algorithm]、大きな整数と文字列を変換しようとするとエラーになるような[「修正」](https://github.com/python/cpython/issues/95778)です。
```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桁なので文字列に変換しようとしたときにエラーとなっています。前のバージョンでは難なく動いていたので、パッチリリースで後方互換性をぶっ壊した[^patch]ことなどが議論の的となっています[^dispute]。

# 西暦10^4300年問題

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

```python
import calendar

year = eval(input("year?"))
month = eval(input("month?"))
calendar.TextCalendar().prmonth(year, month)
```
ユーザーに年と月を入力してもらい[^vulnerability]、[`calendar`モジュール](https://docs.python.org/ja/3/library/calendar.html)の[`TextCalendar`クラス](https://docs.python.org/ja/3/library/calendar.html#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ならね[^zeller]。
```
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}$年になると途端に動かなくなるプログラムが書けてしまいました[^limitation]。西暦$10^{4300}$年問題の爆誕です[^rfc2550]。遠い将来、陽子崩壊[^proton-decay]や真空崩壊[^vacuum-decay]など、[セカイ系主人公](https://dic.pixiv.net/a/%E9%80%83%E3%81%92%E3%81%A1%E3%82%83%E3%83%80%E3%83%A1%E3%81%A0)ですら全力で逃げるレベルの、幾度もの破滅の危機を乗り越えた後の人類に降りかかるのは2022年9月に仕込まれた「バグ」なのでした[^ultimate-fate]。子孫がんばれ。超がんばれ。

[^quadratic]: （マシンによって違う）具体的に何秒かという数字よりも、サイズ$n$の入力に対し計算量が$O(n^2)$で増えていくのがヤバいです。

[^pypy]: ざっくりと第0次近似でPython $\simeq$ CPythonとして説明しています。CPython以外なら、たとえば[PyPy](https://www.pypy.org/)での議論は[ここ](https://foss.heptapod.net/pypy/pypy/-/issues/3805)。

[^algorithm]: もうちょっとマシなアルゴリズムにしようよという議論は[こちら](https://github.com/python/cpython/issues/90716)。

[^patch]: [セマンティックバージョニング](https://semver.org/lang/ja/)によると、パッチバージョンを上げるときは後方互換性を伴ったバグ修正しかしてはいけないはず。

[^dispute]: [ここ](https://github.com/python/cpython/issues/95778)とか[ここ](https://discuss.python.org/t/int-str-conversions-broken-in-latest-python-bugfix-releases/18889)とか[ここ](https://www.reddit.com/r/Python/comments/x8ag01/int1_4301_will_raise_valueerror_starting_with/)とか[ここ](https://lwn.net/Articles/907572/)とか[ここ](https://github.com/python/cpython/issues/96834)とか。

[^vulnerability]: ユーザー入力をサニタイズせずそのまま`eval()`に食わせていますが、良い子は真似しないでね。

[^zeller]: このカレンダーが合っていることは、[ツェラーの公式](https://ja.wikipedia.org/wiki/%E3%83%84%E3%82%A7%E3%83%A9%E3%83%BC%E3%81%AE%E5%85%AC%E5%BC%8F)を使うと（$y=400n-1$（$n$は整数）と書けるのでいろいろと簡単になって）すぐに分かります。

[^limitation]: 本当は、年と月を入力しなくても勝手に現在日時を取得してカレンダーを表示するプログラムにしようと思ったのですが、Python標準の[`datetime`モジュール](https://docs.python.org/ja/3/library/datetime.html)は[9999年までしか扱えない](https://docs.python.org/ja/3/library/datetime.html#datetime.MAXYEAR)のでした。恐るべし、[西暦10000年問題](https://ja.wikipedia.org/wiki/%E8%A5%BF%E6%9A%A610000%E5%B9%B4%E5%95%8F%E9%A1%8C)。

[^rfc2550]: 西暦$10^{4300}$年問題を含めたいわゆる「Y10K and Beyond」問題についての解決策はすでに[RFC 2550](https://www.ietf.org/rfc/rfc2550.txt)（[和訳](http://www.cam.hi-ho.ne.jp/mendoxi/rfc/rfc2550j.html)）として提案されており、西暦$10^{18308}$年まで例を交えながら論じられています。なお、このRFCが公開されたのは1999年**4月1日**です。

[^proton-decay]: 2022年10月現在、陽子の平均寿命の実験的下限は信頼水準90%で$3.6\times 10^{29}$年（invisible mode、ソースは[これ](https://pdg.lbl.gov/2022/web/viewer.html?file=../tables/rpp2022-sum-baryons.pdf)とか[これ](https://arxiv.org/abs/1812.05552)とか）。

[^vacuum-decay]: [これ](https://arxiv.org/abs/1707.08124)によると信頼水準95%で$10^{65}$～$10^{1383}$年くらいに起きます。[こちら](https://arxiv.org/abs/1707.09301)も参照のこと。

[^ultimate-fate]: $10^{4300}$年まで人類がPythonを使っているのか、それまでこの「バグ」が修正されないのか、内部表現の桁溢れではないので本質的な問題ではないとか、まだ西暦が使われているのか、グレゴリオ暦なのか、人類が生き延びていたとしてそれは「人類」なのか、そもそも宇宙はまだあるのかなど、異論は認める。