2024.06.24 ブロックチェーン

AONT（All-Or-Nothing Transform）とは？仕組み・秘密分散との違いとTypeScript実装

AONT（All-Or-Nothing Transform、オール・オア・ナッシング変換）は、秘密鍵をいっさい使わない可逆な前処理で、変換後のブロックが1つでも欠けると元データのどの部分も復元できないという性質を持ちます。1997年にRSA暗号の共同発明者であるRonald L. Rivestが発表しました。この記事は、Rivestの原論文とAONT-RSの原論文、IBM Cloud Object Storageの公式資料の原文に当たって書いています。

まとめ：AONTは鍵を持たない前処理、秘密分散になるのはAONT-RSから

  • AONTは暗号ではありません。原論文が「秘密鍵の情報をまったく使わないので、それ自体は暗号化ではない」と明記しています。全ブロックが揃えば誰でも元データに戻せます。
  • 第一の動機は、40ビット鍵という輸出規制下でも総当たり攻撃を割に合わなくすること。攻撃者のコストは暗号文のブロック数 t 倍になり、正規の送受信者は約3倍で済みます。
  • 「RSAを強くするために考案された」という説明は因果が逆です。原論文はパッケージ変換を、RSA用の前処理であるOAEP（Bellare-Rogaway、1994年）の特殊ケースとみなせる、と位置づけています。
  • 単体では秘匿になりません。後段に通常の暗号化を置くか、Reed-Solomon符号と組み合わせて分散保管する（AONT-RS）ことで初めてデータ保護として成立します。
  • AONT-RSはShamirの秘密分散と違い、安全性は情報理論的ではなく計算量的です。その代わり b バイトのファイルの総保管量が nb から n(b + wA) ÷ k に下がります。
  • 短いデータへの適用には既知の落とし穴があります。小さい暗号文を分散すると情報が漏れる2つの経路が2016年に指摘されました。

「秘密鍵を使わない可逆変換」というAONTの定義

原論文が示す3条件と、乱数化が必須になる理由

Rivestはメッセージ列 m1, m2, …, ms を疑似メッセージ列 m’1, m’2, …, m’s’ に写す変換 f が、次の3条件を満たすときにAONTと呼んでいます。

  • 可逆であること（疑似メッセージ列から元のメッセージ列を得られる）
  • 変換とその逆変換がどちらも多項式時間で計算できること
  • 疑似メッセージのブロックが1つでも欠けていると、どのメッセージブロックについても、いかなる関数値も計算できないこと

3番目が「オール・オア・ナッシング」の本体です。原論文はさらに「AONTは必ず乱数化されていなければならない」と注意しています。決定的な変換だと既知平文攻撃で疑似メッセージが分かってしまい、また第1ブロックを計算する決定的関数が存在してしまって3番目の条件と矛盾するためです。実装では毎回ランダムな鍵を引くことが仕様の一部だ、と読んでください。

AONTの構成はRivestのパッケージ変換だけではありません。OAEPがAONTになることをランダムオラクルモデルで示したBoykoの結果（1999年）や、暗号学的仮定を置かないStinsonの線形AONTが後に続きました。「aont」で検索して論文に当たると、この3系統の名前が出てきます。

暗号化との違い：鍵が無いので全ブロック揃えば誰でも復元可能

原論文の表現は明快です。「the all-or-nothing transformation is not itself “encryption,” since it makes no use of any secret key information（AONTはそれ自体が暗号化ではない。秘密鍵の情報をまったく使わないからだ）」。AONTは誰でも実行でき、誰でも逆変換できる公開の変換であり、秘匿を担うのは後段の暗号化のほうです。

この一点を外すと設計を誤ります。「AONTをかけたから安全」ではなく、「AONTをかけたうえで、全ブロックが揃わない状況を物理的に作る」のが正しい使い方です。分散保管や後段暗号化と組み合わせて初めて機密性が生まれます。鍵を安全に保管する話をしているなら、それはAzure Key Vaultのような鍵管理サービスの領域であり、AONTの守備範囲とは別物です。

Rivestが1997年に示した第一の動機と、「RSA強化のため」説のズレ

原論文の書き出しは総当たり攻撃の話から始まります。「Our primary motivation is to devise means to make brute-force search more difficult, by appropriately pre-processing a message before encrypting it（我々の第一の動機は、暗号化前にメッセージを適切に前処理することで総当たり探索を困難にする手段を考案することだ）」。背景に挙げられているのは、56ビットのDES鍵がすでに心もとないという当時の指摘（Blaze らの共同報告、1996年）と、輸出規制で40ビット鍵に縛られる状況です。

効果は数字で示されています。AONTを前処理として噛ませると、攻撃者は鍵候補ごとに暗号文全体を復号しないと当たり判定ができないため、総当たりのコストが暗号文のブロック数 t 倍になります。原論文の例は8メガバイトのメッセージを40ビットDES鍵で送るケース。作業量は通常のCBCモードの約100万倍に膨らみ、100万は約220なので、原論文いわく「攻撃者にとっては40ビット鍵ではなく60ビット鍵を破らされている感覚」になります。正規の利用者が払う代償は全体で約3倍にとどまります（変換コストが暗号処理の約2倍）。

攻撃者と正規利用者のコスト増加が非対称になる。これがAONTの設計思想です。

では日本語記事でよく見る「もともとRSA暗号の強度を上げるために考案された」はどうでしょうか。原論文の第5節には確かにRSAが登場し、「AONTはRSA暗号の前段で有用であり、Coppersmith らの related message 攻撃などを防ぐ」と述べられています。ただし続く一文が肝心です。「パッケージ変換は、Bellare と Rogaway が optimal asymmetric encryption（OAEP）の前処理として提案した simple embedding scheme の特殊ケースとみなせる」。OAEPは1994年のEUROCRYPTで発表されたRSA用の前処理であり、時系列でも位置づけでも先にあるのはOAEPのほうです。AONTがRSAを強くするために生まれたのではなく、RSA前処理として既にあった構成の一般化としてAONTが定義された、と読むのが原文に忠実です。

パッケージ変換の計算手順（式と各ブロックの役割）

Rivestが具体策として示したのがパッケージ変換（package transform）です。E をブロック暗号、K0 を公開の固定鍵として、次のように計算します。

  • パッケージ変換用の鍵 K’ をランダムに選ぶ（原論文の例は128ビットのRC5鍵）
  • i = 1..s について m’i = mi XOR E(K’, i)
  • hi = E(K0, m’i XOR i) を求め、最終ブロックを m’s+1 = K’ XOR h1 XOR … XOR hs とする

前半はカウンタモードの暗号化とほぼ同じ形で、違いは鍵が固定ではなく毎回ランダムに選ばれる点だと原論文自身が説明しています。要は、その乱数鍵 K’ を最終ブロックに「全ブロックのハッシュで隠して」同梱している構造です。逆変換では、まず疑似メッセージの先頭 s ブロックから hi を計算し直して最終ブロックとXORすることで K’ を取り戻し、その K’ で各ブロックを元に戻します。ブロックが1つでも欠ければ h の総和が合わず、K’ の復元に失敗して全ブロックが読めません。

K’ は秘密の共有鍵ではなく疑似メッセージ内で開示される値なので、後段の暗号モードの鍵長制限（当時なら40ビット）に縛られない、と原論文は補足しています。

秘密分散との関係：AONT-RSがしきい値法になる仕組み

AONT-RSの構成：canaryを付けてから暗号化し、組織符号で分散する

「AONT＝秘密分散法の一種」という説明を見かけますが、正確には、AONTに消失訂正符号を足して (k, n) しきい値法に仕立てたものがAONT-RSです。CleversafeのJason K. Reschとテネシー大学のJames S. Plankが FAST 2011 で発表しました。原論文の図3が示す順序は次のとおりです。

  • 既知の固定値を持つ1ワード「canary」をデータ末尾に付ける
  • ランダム鍵 K を選び、canaryを含むデータを暗号化する。各ワードは ci = di XOR E(K, i+1)（E はAESなど）
  • 暗号化後の s+1 個のコードワードのハッシュ h を SHA-256 などで取り、cs+1 = K XOR h を末尾に付ける（この差分ブロックまで含めてAONTパッケージ）
  • パッケージを組織符号化した（systematic）Reed-Solomon符号で n 個のスライスに分散し、k 個集まれば復元できるようにする

canaryを暗号化の前に入れるのが要点です。スライスが1ビットでも書き換われば再計算したハッシュが変わり、復元される K が狂い、復号結果のcanary位置が既知の固定値と一致しなくなります。ハッシュのなだれ効果をそのまま完全性チェックに転用した設計です。

Shamir法との比較：保管量は n 倍から約 n ÷ k 倍へ

方式 b バイトの総保管量 安全性 鍵の保管
Shamir の秘密分散 (k, n) nb 情報理論的 不要
Rabin の IDA (k, n) nb ÷ k 多くの環境で許容不可（原論文表現） 不要
AONT-RS (k, n) n(b + wA) ÷ k 計算量的 不要

wA はAONTのワード長で、差分ブロックとcanary分の上乗せです。b が大きければ誤差なので、実質は Rabin と同じ n ÷ k 倍と考えて構いません。1GBのファイルを3-of-6で置くなら、Shamir法は6GB、AONT-RSは約2GBです。Shamir法は無限の計算資源を持つ攻撃者にも耐える情報理論的安全性を持ちますが、符号化に O(knb) の演算も要します。AONT-RSは安全性を計算量的なものへ落として、この差を埋めます。原論文の著者らは「wA が十分大きければ、攻撃者はスライスが特定のデータを保持していることを検証することすら計算量的に不可能」であり、機能的には情報理論的安全性と等価だという立場です。

この論文の第一著者はCleversafeの開発者で、原論文の第8節はAONT-RSを「同社が販売するストレージソフトウェアおよびアプライアンスの機能」と記しています。CleversafeはIBMが2015年11月6日に買収を完了し、製品はIBM Cloud Object Storage（COS）へ引き継がれました。

IBM Cloud Object Storageに残るAONT（SecureSlice）

IBMの公式資料（Redpaper REDP-5537）は、COSのデータ保護を「SecureSliceによる保存時暗号化」と「Information Dispersal Algorithmによる消失訂正符号化と分散」の2段階と説明し、SecureSliceについて「uses an all-or-nothing-transform (AONT) to encrypt the data」と名指ししています。処理手順として挙げられているのは、整合性チェック値の付加、乱数鍵の生成、暗号化、暗号化データのハッシュ計算、ハッシュと鍵のXOR、結果の付加という6ステップ。AONT-RSの論文とそのまま同じ流れで、canaryは「整合性チェック値」と呼ばれています。

実装の現在地も追記しておきます。COSは4MiBのセグメント単位で処理し、ソフトウェア3.14.6でAES-GCM-256が追加されました。既定だったAES-128に比べて最大15%高速で、以後は新規vaultの推奨・既定アルゴリズムです。設定を変えても既存オブジェクトは再暗号化されない点も公式資料に明記されています。1997年の論文の構成が、現役の商用オブジェクトストレージにそのまま名前と手順を残しているわけです。なお同資料はAONTを「a type of encryption」と書いており、Rivestの「暗号ではない」という定義とは語の使い方が違います。製品文脈では鍵付き暗号まで含めてAONTと呼ぶ、と理解しておくと混乱しません。

TypeScriptによるパッケージ変換の実装と欠損時の挙動

node:crypto だけで書くパッケージ変換

外部ライブラリなしで書けます。ブロック暗号 E にはAES-128-ECBを1ブロックだけ使い（パディングを切ってブロック暗号そのものとして呼ぶ）、K0 は公開の固定鍵なのでゼロ埋めにしています。

import { createCipheriv, randomBytes } from "node:crypto";

const BLOCK = 16;
const K0: Buffer = Buffer.alloc(BLOCK, 0x00); // 公開の固定鍵。秘密ではない

const ecb = (key: Buffer, block: Buffer): Buffer => {
  const c = createCipheriv("aes-128-ecb", key, null);
  c.setAutoPadding(false);
  return Buffer.concat([c.update(block), c.final()]);
};
const ctr = (i: number): Buffer => {
  const b = Buffer.alloc(BLOCK);
  b.writeUInt32BE(i, 12);
  return b;
};
const xor = (a: Buffer, b: Buffer): Buffer => {
  const o = Buffer.alloc(BLOCK);
  for (let i = 0; i < BLOCK; i++) o[i] = a[i] ^ b[i];
  return o;
};
const split = (buf: Buffer): Buffer[] => {
  const pad = BLOCK - (buf.length % BLOCK);
  const padded = Buffer.concat([buf, Buffer.alloc(pad, pad)]); // PKCS#7
  const out: Buffer[] = [];
  for (let i = 0; i < padded.length; i += BLOCK) out.push(padded.subarray(i, i + BLOCK));
  return out;
};

export function packageTransform(message: Buffer): Buffer[] {
  const K = randomBytes(BLOCK);                       // 毎回引き直す
  const pseudo = split(message).map((m, i) => xor(m, ecb(K, ctr(i + 1))));
  const last = pseudo.reduce((acc, mi, i) => xor(acc, ecb(K0, xor(mi, ctr(i + 1)))), K);
  return [...pseudo, last];                           // 末尾が K を隠したブロック
}

export function recoverBlocks(pseudo: Buffer[]): Buffer[] {
  const body = pseudo.slice(0, -1);
  const K = body.reduce((acc, mi, i) => xor(acc, ecb(K0, xor(mi, ctr(i + 1)))), pseudo[pseudo.length - 1]);
  return body.map((mi, i) => xor(mi, ecb(K, ctr(i + 1))));
}

export function packageInverse(pseudo: Buffer[]): Buffer {
  const b = Buffer.concat(recoverBlocks(pseudo));
  const n = b[b.length - 1];
  if (n < 1 || n > BLOCK) throw new Error("復元失敗: パディング長が不正");
  return b.subarray(0, b.length - n);
}

ECBモードが出てくると身構えるかもしれませんが、ここでは平文をECBで暗号化しているのではなく、カウンタ値 i を1ブロックだけ暗号化して鍵ストリームを作っています。パッケージ変換の定義どおりの使い方です。Rivestのパッケージ変換自体はパディングを規定していないため、PKCS#7を足したなら逆変換側で必ずパディング長を検証してください。検証を省くと、壊れたデータに対して例外を出さずに長さの狂ったバッファを返します。

1ブロック欠損で先頭の平文まで別物になることの確認

Node.js v26.5.0 は型注釈付きの .ts をそのまま実行できます。復元後の先頭ブロックを16進で比べると、欠損の影響が決定的に見えます。

const msg = Buffer.from("秘密分散の前処理としてAONTを使う");
const pseudo = packageTransform(msg);
console.log(`元データ ${msg.length} バイト -> 疑似メッセージ ${pseudo.length * BLOCK} バイト`);
console.log("復元:", packageInverse(pseudo).toString());

const lost = pseudo.slice(0, -1).concat(Buffer.alloc(BLOCK, 0x00)); // 最終ブロックを潰す
console.log("正常時の先頭ブロック:", recoverBlocks(pseudo)[0].toString("hex"));
console.log("欠損時の先頭ブロック:", recoverBlocks(lost)[0].toString("hex"));

実行すると「元データ 46 バイト -> 疑似メッセージ 64 バイト」「復元: 秘密分散の前処理としてAONTを使う」と出て、正常時の先頭ブロックは何度実行しても e7a798e5af86e58886e695a3e381aee5（「秘密分散の」のUTF-8）になります。対して欠損時の先頭ブロックは実行のたびに違う乱数値です。潰したのは末尾の1ブロックなのに、先頭の平文が別物になる。K’ が復元できず、全ブロックの鍵ストリームが総崩れになるからです。

サイズの増加は46バイトから64バイト、パディングと追加1ブロック分だけです。もう一点、欠損時に packageInverse が必ず例外を出すわけではありません。壊れた末尾バイトが偶然1〜16に収まればパディング検証を通ってしまいます。だからAONT-RSは既知固定値のcanaryを別に持っているのだと考えると、あの設計の意味が腑に落ちるはずです。

採用判断：AONTが効く場面と、選ぶべきでない条件

短い平文への適用が危険な理由（2016年に指摘された2つの漏えい）

AONT-RSをそのまま小さいデータに適用してはいけません。Liqun Chen、Thalia M. Laing、Keith M. Martin の3氏は IACR ePrint 2016/1014（AFRICACRYPT 2017 収録、pp.40-57）で、AONT-RSを一般化したうえで「小さい暗号文を分散する場合に情報が漏れる2つの経路がある」と指摘しています。同論文は漏えいを防ぐ方法を示し、ランダムオラクルモデルでの計算量的秘匿性の証明を与え、さらに一部の参加者が誤ったシェアを出しても復元できるロバスト版へ拡張しています。

実務上の含意は単純です。設定値やパスワード程度の短いデータを分散したいなら、素のAONT-RSを自前実装せず、この論文が示す対策済みの構成か、短いデータでも安全性が落ちないShamir法を選んでください。データ長が短いほどAONT系の前提は崩れます。

性能のボトルネックはReed-Solomon符号ではなく暗号とハッシュ

AONT-RSの原論文にある実測値（OpenSSL 0.9.8k、ブロック長8KB）は、AES-256が143.30MB/s、SHA-256が160.03MB/s、両者を通すAONT全体で75.60MB/s です。対してReed-Solomon符号化は30構成の平均で965.61MB/s（標準偏差11.42MB/s）。桁が違います。分散ストレージの速度が出ないときに消失訂正符号のパラメータをいじっても効きません。見るべきは暗号とハッシュの実装です。

この構成が商用で選ばれた理由も同じ実測に出ています。アーカイブストレージPOTSHARDSと同じ3-of-5構成で比べると、AONT-RS（高セキュリティ側）は65.4MB/s、Shamir法は64.4MB/s とほぼ同速。速度が変わらないまま保管量が3分の1になります。ただしこれは2011年の測定で、現在のCPUはAES-NIでAESを桁違いに速く処理します。自環境で測り直すのが前提です。

AONTを選ぶべきでない条件：単一サイト保管・MPC入力・定型データの秘匿

第一に、単一サイトにデータを置くだけの構成。全ブロックが同じ場所にあるならAONTは何も守りません。鍵管理サービスと暗号化の組み合わせのほうが確実です。HashiCorp Vaultのようなシークレット管理基盤で鍵を握れる環境なら、そちらを選んでください。

第二に、秘密計算（MPC）の入力共有。AONT-RSのスライスはReed-Solomon符号なので暗号文に対しては線形ですが、その暗号文と平文はAESと乱数鍵で結ばれているため、平文に対する線形性は失われています。シェアを足しても平文の和にはなりません。MPCが目的ならShamir法や加法的秘密分散を使います。

第三に、カード番号や個人番号のような定型データを業務システムから隠したいだけの場合。この用途は分散保管よりもトークナイゼーションのほうが運用が軽く済みます。AONTが向くのは、複数サイトへ分散でき、かつ鍵の保管場所を作りたくない大容量データです。

よくある質問

AONTと秘密分散は同じものですか？

別物です。AONTは秘密鍵を使わない可逆な前処理で、それ自体は (k, n) しきい値法ではありません。全ブロックが揃わないと復元できない、という性質を持つだけです（AONT-RSの論文はこれを (s+1, s+1) しきい値法とみなせる、と表現しています）。AONTの出力をReed-Solomon符号などで n 個に分散して初めて、k 個集めれば復元できる秘密分散として機能します。日本語記事で「AONTは秘密分散法の一つ」と説明されるのは、この組み合わせを指していることがほとんどです。

AONTだけでデータを秘匿できますか？

できません。原論文が「秘密鍵の情報を使わないので暗号化ではない」と明記しているとおり、疑似メッセージが全部揃えば誰でも元データに戻せます。秘匿を得るには、後段で通常の暗号化を行うか（Rivestが想定した使い方）、分散保管して攻撃者が全スライスを集められない状況を作る必要があります。

AONTで変換するとデータサイズはどれくらい増えますか？

ブロック1個分とパディングだけです。この記事の実装では46バイトの平文が64バイトになりました（3ブロック＋鍵を隠した1ブロック）。分散まで含めると、Shamirの秘密分散が b バイトのファイルに対して nb バイトを要するのに対し、AONT-RSは n(b + wA) ÷ k で済みます。1GBを3-of-6で置けば6GBと約2GBの差です。この保管効率が、分散ストレージでAONT-RSが選ばれる主な理由になっています。

AONT-RSは秘密計算（MPC）に使えますか？

向きません。スライスは暗号文に対しては線形ですが、平文に対する線形性がAESで断ち切られているため、シェア同士を足したり掛けたりしても意味のある結果になりません。シェアのまま計算したいなら、加法的秘密分散やShamir法を使ってください。AONT-RSの狙いは計算ではなく、保管効率と鍵管理の排除にあります。

実装で使う暗号アルゴリズムとハッシュは何を選べばよいですか？

AONT-RSの原論文はAES-256とSHA-256の組（高セキュリティ側）と、RC4-128とMD5の組（高速側）を比較していますが、後者は2011年時点の選択肢です。RC4もMD5も現在は使いません。IBM Cloud Object Storageも3.14.6以降はAES-GCM-256を既定にしています。AES-256系とSHA-256を基本に、AES-NI対応環境で実測してから決めるのが妥当です。Rivestのパッケージ変換の側は、E に使うブロック暗号を任意に選べる設計になっています。

関連記事

資料請求

RELATED POSTS 関連記事

一覧へ戻る