RSAに対するフェルマー攻撃

はじめに（Introduction）

RSAの鍵ペアの生成方法にミスがあり脆弱性となってしまった実装例があったようです。
元の文献を機械翻訳（ちょっと修正）してみます。
原文のデモをやってみたところ、案外動いたので先にデモを記します。

デモ（Demo）

まずは、素数$p$と$q$を生成して$N$を求めるところです。
※：鍵長が2048bitなので多少時間がかかります。
問題となったライブラリがこのようなロジックであったかは不明ですが、翻訳した資料を参考に作成しています。

import random as rnd
import sympy

key_length = 2048
distance = 10000

p = 0
q = 0

# 乱数Xを生成する。
X = rnd.randrange(2, pow(2, key_length))
for i in range(distance):
  # 乱数Xを生成し、Xの次の素数を探索し、それをpとして使用する。
  # pの次の素数を探索し、それをqとする。
  if sympy.isprime(X+i):
    if p == 0:
      p = X + i
    elif q == 0:
      q = X + i
      break

N = p * q

if p > 0 and q > 0:
  print('p:', p)
  print('q:', q)
  N = p * q
  print('N:', N)
else:
  print("Not found!")

無事に$p$、$q$、$N$を生成できました。

p: 9163378376717311892759896790709874300966750864559366002850511560483289442694938524371536081394826360219831218372600953278212991300807322321661081276951933103914701695370758044798746081504842558400345289682449481886671521761200653758803217979571859303042229856285712216457977509930641541741829391994680979277814996883564209816622422745240098425979554433781556268409710036195179160807729930231193303213294956135508383309119484334577201514451117200542518622794209785837919527949534508116519230131217571802776102670003367369643619307360835763485982106832204637148306150932075798650642571927166020916736921962214779959139
q: 9163378376717311892759896790709874300966750864559366002850511560483289442694938524371536081394826360219831218372600953278212991300807322321661081276951933103914701695370758044798746081504842558400345289682449481886671521761200653758803217979571859303042229856285712216457977509930641541741829391994680979277814996883564209816622422745240098425979554433781556268409710036195179160807729930231193303213294956135508383309119484334577201514451117200542518622794209785837919527949534508116519230131217571802776102670003367369643619307360835763485982106832204637148306150932075798650642571927166020916736921962214779959739
N: 83967503274890397950441874775460105392228780582913639886799470415981344025760089149696405718773843220528382204619569220502822200189434065959554301956893966946305218522454689794822620406473018682778525851935444782479115622878482755215142190490253121349057806352320166939469188947073637697664336563477426805606192084504665172140855581520176556083809442308747148621688164316646336400762923921670815415549968171606346231879817954556798417471812553833594373794095213621456086554912876225268217475366497922058419432429909975412038735367335741304892135296148172837249388921659799756040703281143581920784285808085648038534294955481798053608838358717332784074779821750240032235189980618155613461284373557293849849257836256346018722408325086491664008889759172300710703861298006566884773432216670844308514126737839324406165118361746848620588088186334903739087475682260196196999601492232251552224593571617187625068948877036878913967385555077085094892113507954382677046861294473908527963835250168136824581405857096942710246755793268817124788836774485588856604460840208143831626048449124790862535193828550823757888180038315547602790158112826512399467871055898397596936613912462579648887048270695653174582453284431509492834510267029612618485104721

$N$から$p$と$q$を逆算してみます。
計算の途中で平方数（整数での近似値）を算出する必要があるので、ニュートン法を用いたロジックを使用します。

# https://jablogs.com/detail/1515
def isqrt(n):
  x = n
  y = (x + 1) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

# 素数が近ければ、aはNの平方根に近い。
a = isqrt(N)
b = 0

for i in range(distance):
  # このため、Nの平方根から始めて、一周するごとに1ずつ推測を増やしていけば、aの値を推測することができる。
  a = a + 1
  # それぞれの推測に対して、b^2=a^2−Nを計算することができる。
  b2 = a*a - N
  t = isqrt(b2)
  # その結果が平方数であれば、aを正しく推測したことが分かる。
  if t*t == b2:
    b = t
    break

if b > 0:
  print('a:', a)
  print('b:', b)
  # ここから、p=a-b と q=a+b を計算することができる。
  pp = a - b
  qq = a + b
  print(p == pp)
  print(q == qq)
else:
  print("Not found!")

見事に逆算できました。

a: 9163378376717311892759896790709874300966750864559366002850511560483289442694938524371536081394826360219831218372600953278212991300807322321661081276951933103914701695370758044798746081504842558400345289682449481886671521761200653758803217979571859303042229856285712216457977509930641541741829391994680979277814996883564209816622422745240098425979554433781556268409710036195179160807729930231193303213294956135508383309119484334577201514451117200542518622794209785837919527949534508116519230131217571802776102670003367369643619307360835763485982106832204637148306150932075798650642571927166020916736921962214779959439
b: 300
True
True

以下にソースコードがありますので、実際にやってみてください。
https://gist.github.com/tnakagawa/def2f317f2a365387d95d21a8e17e441

翻訳（Translation）

RSAに対するフェルマー攻撃（Fermat Attack on RSA）

はじめに（Introduction）

原文

In 1643 Pierre de Fermat developed a factorization algorithm. The algorithm allows efficiently calculating the prime factors of a composite number that is the product of two "close" primes.

The RSA encryption and signature algorithm relies on the fact that factorization of large numbers is a hard problem. The RSA public key contains a composite number (usually called N) that is the product of two primes (usually called p and q).

If RSA keys are generated with "close" primes then RSA can be broken with Fermat's factorization algorithm. While this is widely known, to my knowledge no such vulnerable RSA keys have been found in the wild before - up until now.

I applied Fermat's factorization method to large datasets of public RSA keys. I discovered a small number of vulnerable keys that belonged to printers from Canon and Fujifilm (originally branded as Fuji Xerox). The devices use an underlying cryptographic module from the company Rambus.

1643年、ピエール・ド・フェルマーは因数分解アルゴリズムを開発した。このアルゴリズムにより、2つの「近い」素数の積である合成数の素因数を効率的に計算することができるようになった。

RSA暗号と署名のアルゴリズムは、大きな数の因数分解が難しい問題であることを利用している。RSA公開鍵は、2つの素数（通常$p$と$q$と呼ばれる）の積である合成数（通常$N$と呼ばれる）を含んでいます。

もしRSAの鍵が「近い」素数で生成された場合、RSAはフェルマーの因数分解アルゴリズムで破ることができる。このことは広く知られていますが、私の知る限り、これまでそのような脆弱なRSA鍵が野放しになっていることはありませんでした。

私は、公開されているRSA鍵の大規模データセットにFermatの因数分解法を適用してみた。その結果、キヤノンと富士フイルム（元々は富士ゼロックスのブランド）のプリンターに属する少数の脆弱な鍵を発見しました。これらのデバイスは、Rambus社の暗号モジュールを使用しています。

FAQ

フェルマーの因数分解アルゴリズムとは？（What is Fermat's factorization algorithm?）

原文

The idea of Fermat's factorization algorithm is that a product of two large primes can always be written as N=(a-b)(a+b), with a being the middle between the two primes and b the distance from the middle to each of the primes.

If the primes are close then a is close to the square root of N. This allows guessing the value a by starting with the square root of N and then incrementing the guess by one each round.

For each guess we can calculate b^2 = a^2 - N. If the result is a square we know we have guessed a correctly. From this we can calculate p=a+b and q=a-b.

Fermat described this algorithm originally in a letter in 1643. The text of the original letter can be found in Oeuvres de Fermat, page 256, available at the Internet Archive.

フェルマーの因数分解の考え方は、2つの大きな素数の積は常に$N=(a-b)(a+b)$と書くことができ、$a$は2つの素数の間の中央、$b$は中央からそれぞれの素数までの距離とするものである。

素数が近ければ、$a$は$N$の平方根に近い。このため、$N$の平方根から始めて、一周するごとに1ずつ推測を増やしていけば、$a$の値を推測することができる。

それぞれの推測に対して、$b^2 = a^2 - N$を計算することができる。その結果が平方数であれば、$a$を正しく推測したことが分かる。ここから、$p=a+b$と$q=a-b$を計算することができる。

フェルマーはこのアルゴリズムを1643年の手紙の中で最初に説明した。この手紙の原文はOeuvres de Fermat,　256ページに掲載されており、Internet Archiveで見ることができる。

誰が影響を受けるのか？（Who is affected?）

原文

Multiple printers of the Fujifilm Apeos, DocuCentre and DocuPrint series generate self-signed TLS certificates with vulnerable RSA keys. The Fuji Advisory contains a list of all affected printers. (The printers use the brand name Fuji Xerox, but the company has since been renamed to Fujifilm.)

Some Canon printers have the ability to generate a Certificate Signing Request with a vulnerable RSA key. To my knowledge this affects printers of the imageRUNNER and imagePROGRAF series.

Both the Fujifilm and the Canon printers use the Basic Crypto Module of the Safezone library by Rambus. Other products using this module to generate RSA keys may also be affected. This vulnerability got CVE-2022-26320 assigned.

(A previous version of this webpage implied that the Canon and the Rambus issue were two separate, unrelated vulnerabilities. This was incorrect. I have informed Mitre that the previously assigned separate CVE for Canon should be rejected.)

富士フイルムのApeos、DocuCentre、DocuPrintシリーズの複数のプリンターが、脆弱なRSA鍵を持つ自己署名TLS証明書を生成しています。富士フイルムのアドバイザリーには、影響を受ける全プリンターのリストが掲載されています。(これらのプリンターはFuji Xeroxというブランド名を使用していますが、その後Fujifilmに社名変更されています)。

キヤノンの一部のプリンターには、脆弱なRSA鍵でCertificate Signing Requestを生成する機能があります。私の知る限り、これはimageRUNNERとimagePROGRAFシリーズのプリンターに影響します。

富士フイルムとキヤノンのプリンターは両方とも、Rambus社のSafezoneライブラリのBasic Crypto Moduleを使用しています。このモジュールを使用してRSAキーを生成している他の製品も影響を受ける可能性があります。この脆弱性には、CVE-2022-26320が割り当てられています。

(本ウェブページの以前のバージョンでは、キヤノンの問題とRambusの問題は、無関係な2つの別の脆弱性であると示唆されていました。これは誤りです。私はMitreに、以前割り当てられたキヤノンの別のCVEは却下されるべきだと伝えました)。

これはRSAの弱点なのでしょうか？（Is this a weakness in RSA?）

原文

No, RSA libraries with a correct key generation function are not affected.

いいえ、正しい鍵生成機能を持つRSAライブラリは影響を受けません。

どうしてこんなことが起こるのでしょうか？（How can this happen?）

原文

An RSA library is vulnerable if the two primes p and q are close. If the primes are generated independently and randomly then the likelyhood of p and q being close is neglegible.

An RSA library might however implement a flawed key generation algorithm like this:

• Generate random number X.
• Search the next prime after X and use it as p.
• Search the next prime after p and use it as q.

For common RSA key sizes this creates p and q with a difference that is usually in the thousands or lower. This can easily be broken with Fermat's factorization method.

RSAライブラリは、2つの素数$p$と$q$が近い場合に脆弱になります。もし素数が独立してランダムに生成されるなら、$p$と$q$が近い可能性は否定的です。

しかし、RSAライブラリは以下のような欠陥のある鍵生成アルゴリズムを実装しているかもしれない。

• 乱数$X$を生成する。
• 乱数$X$を生成し、$X$の次の素数を探索し、それを$p$として使用する。
• $p$の次の素数を探索し、それを$q$とする。

一般的なRSAの鍵のサイズでは、この方法では$p$と$q$の差は通常数千以下となる。これはフェルマーの因数分解で簡単に破ることができる。

素数はどの程度「近い」と脆弱になるのでしょうか？（How "close" do primes need to be in order to be vulnerable?）

原文

With common RSA key sizes (2048 bit) in our tests the Fermat algorithm with 100 rounds reliably factors numbers where p and q differ up to 2^517. In other words it can be said that primes that only differ within the lower 64 bytes (or around half their size) will be vulnerable.

Up to 2^514 it almost always finds the factorization in the first round of the algorithm. It could be argued that the 100 rounds is therefore excessive, however the algorithm is so fast that it practically does not matter much.

一般的なRSA鍵のサイズ（2048ビット）でのテストでは、100ラウンドのフェルマーアルゴリズムは、$p$と$q$が最大$2^{517}$まで異なる数を確実に因数分解しました。言い換えれば、下位64バイト（またはその半分のサイズ）しか違わない素数は脆弱であると言える。

$2^{514}$までは、ほとんどの場合、アルゴリズムの最初のラウンドで因数分解を見つけることができます。したがって、100ラウンドは過剰であるとも言えるが、このアルゴリズムは非常に高速であるため、実質的にはあまり問題ではない。

素数がランダムに独立して生成される場合、脆弱な鍵は偶然に生成されることがあるのか？（Can vulnerable keys be generated by accident if primes are generated randomly and independently?）

原文

This is almost impossible. For primes to be "close" they would have to be identical at least on their upper 500 bits. The chance of that happening is therefore smaller than 1:2^500.

ほとんど不可能です。素数が「近い」ためには、少なくとも上位500ビットが同一でなければなりません。したがって、それが起こる確率は$1:2^{500}$より小さい。

その鍵はどうやって見つけたんですか？（How did you find those keys?）

原文

I used multiple sets of public keys that I either had access to, that were shared with us by other researchers or that were publicly available.

I found the vulnerable, self-signed Fujifilm keys in recent scans of TLS certificates by Rapid7 (Rapid7 has since closed down access to its scan data, but I performed the tests before that). I found a small number of valid, publicly trusted web certificates in Certificate Transparency logs. By contacting their owners I learned about the Canon printers.

It should be noted that all vulnerable certificates were of relatively recent origin (2020 and later). I believe that this is the reason that no such vulnerabilities were described in previously.

私が入手した、あるいは他の研究者から教えてもらった、あるいは一般に入手可能な複数の公開鍵セットを使用しました。

Rapid7が最近行ったTLS証明書のスキャンで、脆弱な自己署名のFujifilmの鍵を見つけました（Rapid7はその後スキャンデータへのアクセスを閉鎖しましたが、私はその前にテストを実施しました）。私は、Certificate Transparencyのログから、有効で一般に信頼されている少数のWeb証明書を発見しました。その所有者に連絡することで、Canonのプリンターについて知ることができました。

なお、脆弱な証明書はすべて比較的新しいもの（2020年以降）でした。以前、このような脆弱性が記述されていなかったのは、このためだと思います。

SSHは影響を受けますか？（Is SSH affected?）

原文

There are probably no vulnerable SSH implementations creating such keys, though I obviously cannot proove that.

I checked multiple large collections of both SSH host and user keys. I did not find any vulnerable keys.

このような鍵を作成する脆弱なSSH実装はおそらく存在しないでしょう。しかし、それを証明することはできません。

私はSSHのホスト鍵とユーザー鍵の両方の大規模なコレクションを複数チェックしました。脆弱な鍵は見つかりませんでした。

PGP/GnuPG/OpenPGPは影響を受けますか？（Is PGP/GnuPG/OpenPGP affected?）

原文

I applied the algorithm to a dump of the SKS PGP key servers. I found four vulnerable keys. However all these keys had a user ID that did imply they were created for testing.

It is plausible that these keys were not generated by vulnerable implementations, but were manually crafted, possibly by people aware of this attack creating test data.

このアルゴリズムをSKSのPGPキーサーバーのダンプに適用してみました。その結果、4つの脆弱な鍵が見つかりました。しかし、これらの鍵はすべて、テスト用に作成されたことを示唆するユーザーIDを持っていました。

これらの鍵は脆弱な実装によって生成されたものではなく、この攻撃を知っている人がテストデータを作成し、手作業で細工したものである可能性が高いです。

おすすめは？（What do you recommend?）

原文

If you are running one of the affected devices you should make sure that you update the devices and regenerate the keys.

If you are in a position where external users will supply public RSA keys to you then you might want to implement checks for this vulnerability. A typical case for this are certificate authorities. I shared the exploit code with certificate authorities and are aware that some have implemented checks in their certificate issuance process to avoid accepting keys vulnerable to this attack.

You can find Let's Encrypt's implementation of the check in their Boulder software in this pull request.

This vulnerability was found by Hanno Böck. This work was funded in part by Industriens Fond through the CIDI project (Cybersecure IOT in Danish Industry) and in part by the Center for Information Security and Trust (CISAT) at the IT University of Copenhagen, Denmark.

もし、影響を受けるデバイスを使用している場合は、デバイスをアップデートし、キーを再生成することを確認してください。

外部ユーザーからRSA公開鍵を提供される立場にある場合、この脆弱性に対するチェックを実施することをお勧めします。典型的なケースは、認証局です。私は、この悪用コードを認証局と共有し、一部の認証局では、この攻撃に対して脆弱な鍵を受け入れないように、証明書の発行プロセスにチェックを入れていることを承知しています。

Let's Encrypt社のBoulderソフトウェアにおけるチェックの実装は、このプルリクエストで確認することができます。

本脆弱性は、Hanno Böck氏により発見されました。この研究は、CIDIプロジェクト（Cybersecure IOT in Danish Industry）を通じてIndustriens Fondから一部資金提供を受け、デンマークのコペンハーゲンIT大学のCISAT（Center for Information Security and Trust）から一部提供されたものです。

まとめ（Conclusion）

RSAでは大きい素数を生成する部分に処理時間がかかるという問題に対して近くの素数を利用したのだと想像します、それがこのような問題に発展したと思います。
ただ、いまから約380年前に発表された理論が現在の脆弱性を暴くとは、天才フェルマーも想像してなかったと思います。

私も暗号関連の仕組みをいろいろと考えますが、多方面で気を付ける必要があるようです。（難しいなぁ）

参考（References）

• Fermat Attack on RSA(https://fermatattack.secvuln.info/)
• Deepl翻訳(https://www.deepl.com/ja/translator)