NAT越え - GOTO Laboratory

大規模NATを越えるための
UDP Multi Hole Punchingの拡張
コンピュータ・ネットワーク工学科 4年
後藤滋樹研究室
戸部 和洋 (1G06R140-0)
卒業論文審査会
February 1, 2010
Kazuhiro TOBE, GOTO Laboratory,
Dept. of Computer Science and Engineering
1
研究の背景 (1)
Network Address Translator (NAT) の問題
UDP Hole Punching
NATの問題点
• NATは外側から接続できない
• NATの内側のホストのアドレス
は外側からわからない
• インバウンドの開始パケット
(initiation packet) を破棄する NAT
private
address
realm
global address
realm
the
Internet
越え
host-A
NAT-B
host-B
(1)host-Aの外部IP,
外部portがわかる
(2)host-Bの外部IP,
外部portがわかる
(3)host-Bと通信したいな
(5)戻りパケットを
期待して穴が空く
NATは外側から
接続できない
rendezvous
server
NAT-A
(8)戻りパケットと
して転送される
(4) host-Bは(A, P)にいます
host-Bにもお知らせしますね
(6)知らない相手
のパケットは破棄
(7)戻りパケットを
期待して穴が空く
(9)戻りパケットと
して転送される
UDP Hole Punchingによって、NATを越えて相手と直接通信（NAT越え）できる。
Kazuhiro TOBE, GOTO Laboratory,
卒業論文審査会
February
1, 2010 NATに限る。
Dept. ofi.e.
Computer
Science and
Engineering
※ただし、Cone
Symmetric
NATは（普通には）越えられない。
2
既存手法
UDP Multi Hole Punching
• UDP Hole Punching
の改良版
NAT-A
server-A server-B
host-A (Cone NAT)
• 2台のサーバとの通信
によるポート予測
• 低いTTLに設定した
UDPパケットを大量送信
• Symmetric NATをリレー
サーバなしで越えられる
• サーバに低負荷・低遅延
• cf. TURN, ICE, Teredo
(Symmetric NAT) host-B
(7)
Time
Exceeded
(8)
(9)
当時はこれでよかったが・・・
卒業論文審査会
February 1, 2010
NAT-B
Kazuhiro TOBE, GOTO Laboratory,
Dept. of Computer Science and Engineering
(10)
(11)
3
研究の背景 (2)
大規模NAT (Large Scale NAT)
[Huston] G. Huston, “IPv4 Address Report”,
http://www.potaroo.net/tools/ipv4/index.html
• IPv4アドレスの在庫枯渇が迫る (IANA:2011, RIR:2012) [Huston]
• ISPは大規模NAT (Large Scale NAT/
the
Carrier Grade NAT) の配置を計画
global
Internet
• NATの多段接続
• NAT越えが難しくなる
Large Scale
NAT
address
realm
e.g. UPnPは機能しない
• ポート番号の制限
• 同時セッション数の制限
e.g. Google Maps
UDP Multi Hole
Punching
の改良が必要
private
address
realm
home
network
ISP
network
home
NAT
home
network
ISP shared
address
realm
ISP
network
home NAT
home
network
home
network
ポート数の制限
• NATで使えるポート数
にはかぎりがある
• 約60000個 (=216－1024) の
ポート番号を複数のユーザで
共有するため
「虫食い」のGoogle Maps
•
大規模NATにポート数が制限されて、
虫食い状態になったGoogle Maps
• 高速化のため、大量の
セッションを同時に張る
アプリケーションがある
• iTunes (230～270)
• Amazon (90)
• ニコニコ動画 (50～80)
卒業論文審査会
February 1, 2010
このページの図と測定値はすべて以下の文献から引用しています。
[Miyakawa] 宮川 晋, “インターネット10分講座：大規模NAT
（Large Scale NAT:LSN） あるいはキャリアグレードNAT（CGN）”,
http://www.nic.ad.jp/ja/newsletter/No41/0800.html
Kazuhiro TOBE, GOTO Laboratory,
Dept. of Computer Science and Engineering
5
背景のまとめと研究の目的
• 大規模NATや集合団地におけるNATの配置
• NATの多段接続
• 利用可能ポート番号の制限
⇒ UDP Multi Hole Punching（既存のNAT越え手法）による
Symmetric NAT越えの可能性が低下
• 大規模NAT環境においても、UDP Multi Hole Punchingが
効率的に利用できるように技術を拡張
• ポート予測 (Port Prediction)
• Low TTL Value Determination
卒業論文審査会
February 1, 2010
Kazuhiro TOBE, GOTO Laboratory,
Dept. of Computer Science and Engineering
6
Mapping Behavior
• Address and Port-Dependent Mapping (Symmetric NAT)
internal
network
Host-L
Addr: AL
Local
Global
Remote
<AL, PL> <AN, PN> <AR, PR>
<AL, PL> <AN, PN’> <AX, PR’>
<AL, PL> <AN, PN’’> <AX, PR’’>
PN
external network
PR
PN’ NAT
PN’’ Addr: Na
mapped a new port (PN’)
mapped a new port (PN’’)
PL
Hole Punching must predict this new port (PN’’).
PR’
PX
Host-R
Addr: AR
Host-X
Addr: AX (≠AR)
NAT maps a new endpoint when a local host (Host-L) sends a packet to any
external endpoints which Host-L hasn’t sent a packet, if the NAT behaves as
“Endpoint-Independent Mapping”. This NAT was once called “Symmetric NAT”.
ポート予測 (Port Prediction)
• NATが割り当てるポートの規則性を調べ、
次に割り当てられるポートを予測する技術
• これが成功すれば、Hole PunchingでSymmetric NATを越えられる
+1
+1
+1
規則性あり
(Predictable)
Randomの場合
手当たり次第に
大量のパケットを送
信するしかない（最
後の手段）
-4
-4
- 61 !?
規則性なし
(Random)
既存手法の問題点1
ポート予測 (Port Prediction) における問題
問題点1. 同じNATに他のホストがいる場合、
ポート予測が正しく行えない可能性がある
• 自分以外のホストの通信によっても、Symmetric
NATが新しいポートのマッピングを生成するため
• Predictable (e.g. Incremental) にもかかわらず、
Randomと誤判定してしまう可能性がある
「最後の手段」として大量のポートをオープン
⇒ 大規模NATのポートを食い尽くしてしまう
提案手法1
Port Predictionの拡張
解決策1-a. キャプチャ法
• ポート予測中にLAN内のパケットをキャプチャ
• NATの外側の新しいあて先へパケットが流れて
いた場合、その数をポート予測で考慮する
• Predictableであるにもかかわらず、Randomと誤判定
してしまう可能性を減らすことができる
解決策1-b. スキャン法
• 所属するネットワーク上の全IPアドレスを確認
• 応答のあったノード数をポート予測で考慮する
卒業論文審査会
February 1, 2010
Kazuhiro TOBE, GOTO Laboratory,
Dept. of Computer Science and Engineering
10
キャプチャ法 vs. スキャン法
キャプチャ法
利点
利点
• ポート予測に追加時間
がほとんどかからない
欠点
• ユーザモードでも動作
（実装による）
欠点
• 管理者権限 (Windows) /
root権限 (Linux) が必要
• ハブでつながっている
マシンのトラヒックしか
キャプチャできない
卒業論文審査会
February 1, 2010
スキャン法
• 確率的な予測のみ
• スキャンのための時間
がかかる
• 攻撃として検知される
可能性あり (e.g. IDS)
Kazuhiro TOBE, GOTO Laboratory,
Dept. of Computer Science and Engineering
11
Low TTL Value Determination
• UDP Multi Hole PunchingはパケットのTTLを低く
設定1) して送信することで、自分側のNATを越えて、
相手側のNATに到達する前にパケットを破棄する
• Low TTL Value Determination：1) の値を決めるアルゴリズム
• UDP Multi Hole Punching : 「決めうち」
• NATBLASTER :「traceroute の方法」（提案のみ、未実装）
• e.g.) TTL = 2の場合
Time Exceeded
TTL => 0
TTL => 1
卒業論文審査会
February 1, 2010
NAT router
(1st hop)
TTLの値は次の条件を満たしていればよい
TTL > 1 ∧ TTL – 5 < 0 ∴ 1 < TTL < 5
router
(4th hop)
router
(2nd hop)
router
(3rd hop)
NAT router
(5th hop)
12
既存手法の問題点 (2)
Low TTL Value Determination における問題
• NATが多段の場合、自分側の一番外側のNATを越
えて相手側の一番外側のNATに到達する前にTTL
が0になればよいが・・・
• TTL > 2 ∧ TTL – 4 < 0
∴ 2 < TTL < 4
問題点2. NATがいくつ連なっているか判断できない
• Tracerouteで得られたルーターのIPアドレスから、NATか
どうか判断できることがあるが、ICMPを返さないルータがある
NAT router
(4th hop)
NAT router
(2nd hop)
卒業論文審査会
February 1, 2010
NAT router
(1st hop)
router
(3rd hop)
NAT router
(5th hop)
13
提案手法2
Low TTL Value Determinationの方法
解決策2. tracerouteやtracertでhop数を求め、
それを2で割った値をTTLとする
[仮定] NATは経路の両端に存在し、中央にはない（はず）
• 本手法は途中のルーターのIPアドレスを知る（NATか判
定する）必要がないためICMPが返されなくても問題ない
$ tracert 208.77.188.166
Tracing route to www.example.com [208.77.188.166]
over a maximum of 30 hops:
1
2
*
*
*
*
11
12
*
144 ms
*
147 ms
Trace complete.
*
Request timed out.
*
Request timed out.
（省略）
*
Request timed out.
146 ms www.example.com [208.77.188.166]
14
実装
Javaで実装
• 一部、Rubyで実装し、java.lang.Runtime#exec()で実行
• Javaでは、ユニキャストUDPパケットのTTLを設定できないため
• キャプチャ法
• Jpcapを利用
• libpcap / WinPcap のJavaラッパー
• スキャン法
• java.net.InetAddress#isReachable()
• （権限があれば）ICMP ECHO REQUEST
• （なければ）ポート 7 (Echo) で TCP 接続
卒業論文審査会
February 1, 2010
Kazuhiro TOBE, GOTO Laboratory,
Dept. of Computer Science and Engineering
15
実験用ネットワーク
（VMware ESXiによる仮想環境）
home NAT-2
home NAT-1
LSN-1
LSN-2
(flexNES) private
private (flexNES)
(flexNES) global realm (flexNES)
Linux
realm-2
realm-1.1
.2
.1
.2 Sym .1
.2 vs .1
.66
vs
router
.1
.65
(10.0.1.0/24)
(10.0.0.0/24)
vs
vs
virtual switch
virtual switch
(promiscuous mode)
ISP-1 (192.0.2.0 .129 (192.0.2.64/26) ISP-2
shared
.2
shared /26) virtual switch (vs)
.2
.3
address
address
.130
.131
realm
realm
internal host-1,2
internall host-3
(192.168.0.0/24)
(192.168.1.0/24)
external server-1, 2
(192.0.2.128/26)
※Sym = Symmetric NAT
※flexible NAT Emulation Server (flexNES)
= RFC4787に準拠したNATエミュレータ
実験用ネットワーク（論理図）
home NAT-1
private (flexNES)
realm-1.1
.2
LSN-1
LSN-2
(flexNES) global realm (flexNES)
Linux
.2
.1
.1
router .66
.1
.65
(10.0.1.0/24)
(10.0.0.0/24)
.2
.3
home NAT-2
(flexNES) private
realm-2
.2 Sym .1
ISP-1 (192.0.2.0 .129 (192.0.2.64/26) ISP-2
shared
shared /26)
address
address
.130
.131
realm
realm
.2
internal host-1,2
internall host-3
(192.168.0.0/24)
(192.168.1.0/24)
external server-1, 2
(192.0.2.128/26)
※Sym = Symmetric NAT
※flexible NAT Emulation Server (flexNES)
= RFC4787に準拠したNATエミュレータ
まとめと今後の課題
まとめ
UDP Multi Hole Punchingの拡張
• 必要以上のポートをオープンしてしまう問題の解決
• 通信経路上でNATが多段になっていても適応可能
今後の課題
Low TTL Value Determinationにおける仮定の妥当性の検討
• 「NATはエンドホストの近くに集中」
• 「経路の中央付近には存在しない」
卒業論文審査会
February 1, 2010
Kazuhiro TOBE, GOTO Laboratory,
Dept. of Computer Science and Engineering
18
ご清聴ありがとうございました
卒業論文審査会
February 1, 2010
Kazuhiro TOBE, GOTO Laboratory,
Dept. of Computer Science and Engineering
19