Pages

3/20/2013

DNS Tunneling with Iodine

หลังจาก เล่าเรื่องวิธีการ by-pass wifi login ด้วยการใช้ tunneling ไปแล้วในบทความที่แล้ว http://blog.anidear.com/2013/03/use-tunneling-to-bypass-wifi.html

DNS Tunneling

คราวนี้มาลองดูว่าถ้าจะ setup ระบบที่เป็น DNS Tunneling จะต้องทำอะไรบ้าง

โดยในบทความนี้ จะใช้ Iodine ในการทำ
(ภาพจาก http://periodictabledesign.com/wp-content/uploads/s002/iodine.jpg)

Iodine เป็นโปรแกรม open source ที่เอาไว้สำหรับสร้าง tunnel ผ่าน DNS protocol (UDP port 53) โดยตัว iodine จะมีโปรแกรมทั้ง 2 ส่วน ทั้ง client และ server

ที่น่าสนใจอีกอย่างคือ คำว่า iodine (ไอโอดีน) เป็น ธาตุที่มีเลขอะตอมเท่ากับ 53 ซึ่งตรงกับเลข port  ที่ใช้ของ DNS protocol เลย

การติดตั้งฝั่ง Server

Iodine เป็น open source ที่มีการ compile ไว้เรียบร้อยแล้วสำหรับระบบต่างๆ ไม่ว่าจะเป็น Windows, Mac, Linux (FreeBSD,OpenBSD,Gentoo,Debian,Arch,Fedora,Ubuntu,Mandriva,Backtrack), ถึงขนาด Android ก็มี native binary file ให้เลยทีเดียว

เนื่องจาก server ที่ผมใช้เป็น RaspBian (บน Raspberry Pi) ซึ่งมาจากระบบ Debian ก็เลยสามารถใช้ APT เพื่อดึงโปรแกรมมาลงได้เลย ด้วยคำสั่ง
sudo apt-get install iodine
เมื่อลงเสร็จแล้ว iodine จะมีไฟล์ให้รันทั้งแบบ server (ชื่อไฟล์ iodined) และ แบบ client (ชื่อไฟล์ iodine) ทั้งคู่เลย

โดยถ้าจะทดลองรันในแบบ server ก็จะใช้คำสั่งว่า
sudo iodined -f -P test 10.0.0.1 anidear.com
โดย

  • -f  เป็น ตัวบอกให้ iodined รันในโหมดที่แสดงการทำงานของโปรแกรมออกมาทางหน้าจอ
  • -P test  เป็นการตั้ง password ให้กับ tunnel  ในที่นี้ใช้คำว่า test
  • 10.0.0.1  เป็น IP ของเครื่อง server นี้หลังจาก tunnel ได้ถูกสร้างขึ้นแล้ว
  • anidear.com  เป็น ชื่อต้นของ domain ที่จะใช้ในการแทรกข้อมูลในการทำ DNS tunneling เข้าไป

หน้าตาจะออกมาประมาณนี้



การติดตั้งฝั่ง Client

ส่วนฝั่ง client ถ้าจะทดลองในการติดต่อมาหา server ตัวนี้  ก็สามารถลงตัว iodine ด้วยวิธีเดียวกัน (ถ้าเป็น debian base linux) หรือใช้การดาวน์โหลดจาก http://code.kryo.se/iodine/ สำหรับ OS ตัวอื่นๆ

เมื่อติดตั้งฝั่ง client เสร็จแล้ว ก็จะทดลองติดต่อข้อมูลไปหา server ด้วยคำสั่ง
sudo iodine -fP test 192.168.1.33 anidear.com
โดย

  • -f  เป็น การรันในโหมดที่แสดงผลของโปรแกรมผ่านทางหน้าจอ 
  • -P test  เป็น การใส่ password ตอนติดต่อกับ iodined server
  • 192.168.1.33  เป็น หมายเลขไอพี ของ server ที่จะติดต่อไปหา (ซึ่งถ้าเป็นกรณีรันจริงๆ ตรงนี้จะต้องเป็น public IP address ของ server)
  • anidear.com  เป็น ชื่อต้นของ domain ที่จะใช้ในการทำ DNS tunneling

โดยหน้าตาเมื่อลองรันคำสั่งข้างต้น ผลจะออกมาแบบนี้

จะเห็นว่า เมื่อติดต่อสำเร็จ  ฝั่ง client จะเสมือนมีการ์ด network interface ที่ชื่อ "dns0" ขึ้นมา โดยจะถูกจ่าย IP หมายเลข 10.0.0.2 ให้

และ interface ตัวนี้นี่เอง ที่เป็น tunnel ที่เราจะเอาไว้ใช้เหมือนกับ VPN โดยจะให้ข้อมูลที่เราต้องการออก internet วิ่งผ่านช่องทางนี้

อันนี้เป็นการทดสอบเล็กๆน้อยๆกับ tunnel บน dns0 interface นี้


ทีนี้ลองมาดูว่า ข้อมูลที่วิ่งออกวิ่งเข้า โดยผ่าน DNS Tunnel นี่หน้าตาเป็นยังไง

ในรูปนี้ คือการใช้โปรแกรม Wireshark เพื่อทำการดักข้อมูลบน eth0 ซึ่งเป็นการ์ดตัวต้นที่เราใช้สร้าง DNS tunnel (dns0)


นี่เป็นการดักข้อมูล ในขณะที่ฝั่ง client ทำการเปิดหน้าเว็บเพจ ผ่านทาง DNS tunnel ของเรา

เนื่องจาก DNS Tunnel จะแก้ไข DNS packet ให้แตกต่างไปจากธรรมดา เพื่อที่จะยัดข้อมูลลงไปได้ ดังนั้น Wireshark จึงขึ้นแถบสีแดงขึ้นและบอกว่า DNS packet นี้อ่านไม่ออก เพราะมันไม่อยู่ในรูปแบบมาตรฐาน


พอเปิด follow UDP stream จะเห็นว่า ไม่มีส่วนไหนที่อ่านออกเลย
ทั้งๆ ที่ปกติจะใช้การติดต่อแบบ HTTP protocol จะเป็น plain text แปลว่า ข้อมูลควรจะไม่ได้มีการเข้ารหัส และ ควรจะสามารถ เห็นข้อมูลได้โดยตรง ... แต่นี่ไม่เห็นเลย เพราะ iodine ทำการเข้ารหัสข้อมูลไว้ให้ด้วย

ติดตั้งฝั่ง Server ต่อ ให้ใช้งานได้จริง

หลังจากเรารู้แล้วว่าระบบนี้มันใช้งานได้  ก็ถึงเวลาเอาขึ้นไปรันในระบบจริง

ขอสรุปคร่าวๆละกัน

โดย สิ่งที่จะต้องมีคือ

  • public IP address สำหรับ server (อาจจะใช้ เน็ตบ้านและตั้ง router ให้ forward port 53 ก็ได้)
  • domain name
  • เครื่อง server ที่จะเปิดตลอดเวลา
ถ้าลงระบบผ่าน apt-get install เมื่อติดตั้งแล้ว จะมี config ของระบบอยู่ที่ไฟล์ /etc/default/iodine

โดยค่ามาตรฐานเป็น
# Default settings for iodine. This file is sourced from
# /etc/init.d/iodined
START_IODINED="false"
IODINED_ARGS=""
IODINED_PASSWORD=""

เราสามารถ config ได้แบบง่ายๆ ด้วยการรันคำสั่ง
dpkg-reconfigure iodined
ซึ่งจะมีหน้าจอ wizard ให้กด Next ไปเรื่อยๆได้

หรืออาจจะเลือกแก้ไขด้วยตัวเอง  ก็คือแก้ไฟล์ /etc/default/iodine ให้มีค่าเป็นแบบนี้
# Default settings for iodine. This file is sourced from
# /etc/init.d/iodined
START_IODINED="true"
IODINED_ARGS="10.0.0.1 anidear.com"
IODINED_PASSWORD="test"


เมื่อ save ไฟล์แล้วก็เริ่มเปิดการใช้งาน service นี้ด้วยคำสั่ง
sudo service iodined start
และนี่ก็จะจบการติดตั้งฝั่ง Server

หลังจากนั้น ก็ต้องไปยุ่งกับ domain ต่อ โดยการไปตั้งให้ domain หรือ sub-domain ชี้ไปหาเครื่อง server ที่เราติดตั้ง iodined ไว้
โดยจะต้องตั้งค่า DNS ไว้แบบนี้
dns A 202.xxx.xxx.xxx
tunnel NS dns.anidear.com 
โดยบรรทัดแรกจะระบุว่า  sub-domain ที่ชื่อ "dns.anidear.com" จะชี้ไปหา IP หมายเลข 202.xxx.xxx.xxx
และบรรทัดที่สองจะบอกว่า ถ้า sub-domain ชื่อ "tunnel.anidear.com" รองรับการติดต่อด้วย DNS protocol โดยใช้ที่อยู่ IP เดียวกับ "dns.anidear.com"

เมื่อตั้งค่าเสร็จแล้ว  อาจจะทดลองระบบโดยการใช้ตัวเช็ค DNS Tunnel ของผู้สร้าง Iodine ก็ได้
โดยนำ domain ที่ได้ไปเช็คที่ http://code.kryo.se/iodine/check-it/


ถ้าผลลัพธ์ออกมาเป็น
Well done, your iodine setup seems fine!
ก็หมายถึงว่า การติดตั้งสำเร็จ และพร้อมใช้งาน ^_^

ทดสอบการใช้งานผ่าน domain จริง

ทดสอบ connect ผ่านเครือข่าย 3G

$ sudo iodine -fP test 202.xxx.xxx.xxx tunnel.anidear.com
Opened dns0
Opened UDP socket
Sending DNS queries for tunnel.anidear.com to 202.xxx.xxx.xxx
Autodetecting DNS query type (use -T to override).
Using DNS type NULL queries
Version ok, both using protocol v 0x00000502. You are user #0
Setting IP of dns0 to 10.1.1.2
Setting MTU of dns0 to 1130
Server tunnel IP is 10.1.1.1
Testing raw UDP data to the server (skip with -r)
Server is at 192.168.1.33, trying raw login: ....failed
Using EDNS0 extension
Switching upstream to codec Base128
Server switched upstream to codec Base128
No alternative downstream codec available, using default (Raw)
Switching to lazy mode for low-latency
Server switched to lazy mode
Autoprobing max downstream fragment size... (skip with -m fragsize)
768 ok.. 1152 ok.. ...1344 not ok.. ...1248 not ok.. ...1200 not ok.. 1176 ok.. ...1188 not ok.. will use 1176-2=1174
Setting downstream fragment size to max 1174...
Connection setup complete, transmitting data.

แปลว่าต่อติดเรียบร้อย และลองเปิดเว็บแล้วก็ใช้งานได้จริงๆ

Reference


3/19/2013

Use Tunneling To Bypass Wifi Authentication

(ภาพจาก http://wallpaperwise.com/Blue_Binary_Matrix_Tunnel-3361.html)

เมื่อหลายวันก่อน  มีคนพูดถึงวิธีการใช้ UDP Tunneling ในการ bypass Wireless Authentication ที่เปิดให้เข้าแบบไม่มีรหัสผ่านตอน connect (Open System) แต่พอเข้าไปได้แล้วจะเข้าเว็บ จะเด้งเข้าหน้าให้ล็อคอิน

ถ้าพูดเป็นภาษาง่ายๆ ก็คือ เวลาเราไปต่อ wifi ที่ไหน แล้วมันให้เข้าไปได้แต่จะมีหน้าให้กรอก username และ password

โดยปกติ ถ้าไปถึงหน้านี้แล้ว แต่ไม่มี username และ password ก็จะไม่สามารถใช้อินเตอร์เน็ตได้

แต่ว่า  สำหรับ Wifi บางระบบ ที่ไม่ได้ตั้งค่ามาดีๆ เราจะสามารถออกเน็ตได้ โดยไม่จำเป็นต้องรู้ username และ password เลย

คือโดยส่วนมาก ทางผู้ติดตั้งระบบ จะป้องกันไม่ให้เราเข้าเว็บอะไรอย่างอื่นได้  ถ้าอยากเข้าเว็บจะต้องมาทำการล็อคอินก่อน

ซึ่งวิธีตรวจสอบว่าเรากำลังจะเข้าเว็บอะไรหรือเปล่า  ระบบจะตรวจสอบโดยการเช็คว่า เรากำลังจะติดต่อ server บน internet ที่ port 80 หรือเปล่า?

* port 80 คือ ช่องทางมาตรฐานที่ใช้ในการติดต่อแบบ HTTP
** การที่เราเข้าเว็บด้วยการใช้ http:// นำหน้า โดยทั่วไปจะหมายถึง การติดต่อด้วย HTTP protocol โดยใช้ port มาตรฐานคือ port หมายเลข 80

ดังนั้น ถ้าเราติดต่อ server ที่ port อื่นล่ะ ??

1. HTTPS


จริงๆ แล้ว เราสามารถเข้าเว็บด้วยอีกช่องทางนึงคือ การเปลี่ยนไปติดต่อกับ server ด้วยมาตรฐาน HTTPS ซึ่งทำงานบน TCP port 443  ผลลัพธ์ที่ได้คือ นอกจากจะเปิดเว็บได้ตามปกติอย่างที่ HTTP ทำแล้ว เรายังไม่ต้องติดตั้งอะไรเพิ่มไปจากเดิมด้วยเพราะ web browser แทบทุกตัว (Internet Explorer, Chrome, Firefox, Safari, ...) รองรับการเปิดเว็บแบบ HTTPS อยู่แล้ว  แถมการใช้ HTTPS ยังเพิ่มระบบความปลอดภัยเข้าไปอีกด้วย (HTTPS มาจากคำว่า HTTP Secure)

และอีกเหตุผลที่สำคัญคือ การย้ายไปใช้ HTTPS ที่ port 443 เป็นการใช้ port หมายเลขอื่นที่ไม่ใช่หมายเลข 80 ซึ่งส่วนใหญ่ถูกบล็อคเอาไว้ ก็จะทำให้เราติดต่อไปหา server ได้  โดยไม่ต้องกรอก username และ password เลย

การใช้ HTTPS ดูเหมือนจะมีข้อจำกัดอย่างนึงว่า เครื่อง server ที่รอรับปลายทางจะต้องเปิดรองรับการติดต่อด้วย HTTPS (ผ่าน port 443) ด้วย  ยกตัวอย่างระบบที่ใช้ได้ เช่น https://www.facebook.com , https://www.google.com , https://www.twitter.com เป็นต้น

ส่วนเครื่อง server ไหนไม่รองรับ  ถ้าเราติดต่อเข้าไป ก็จะพบว่า หน้าตาจะเป็นเช่นนี้


จะเห็นว่า ถ้าต่อด้วย http:// ปกติ (ติดต่อ server ที่ port 80)  server มีการตอบสนองได้ปกติ แต่ว่า ถ้าใช้ https:// (ติดต่อ server ที่ port 443) จะไม่สามารถเปิดได้  แสดงว่า  เว็บนี้รองรับแค่ HTTP อย่างเดียวเท่านั้น

(ป.ล. อาจจะแก้ได้ด้วยการใช้ "HTTPS Everywhere" อันนี้ไม่แน่ใจ เพราะยังไม่ได้ลอง)

2. UDP


Wifi บางระบบ อาจจะตั้งให้บล็อคการติดต่อออกไปหา server ข้างนอกที่ใช้ TCP ทั้งหมด  ซึ่งมันเป็นวิธีที่ค่อนข้างมีเหตุผล เนื่องจากการติดต่อส่วนใหญ่ระหว่าง client กับ server มักจะเลือกใช้ TCP protocol เกือบทั้งหมด เช่น การเปิดหน้าเว็บ (HTTP, HTTPS) , การเช็ค email (POP3, SMTP, IMAP), การแช็ต(MSN, Line, Whatsapp) และอีก ฯลฯ  ล้วนแต่ใช้ TCP ทั้งสิ้น

แต่ว่า  ก็อย่าลืมว่า เรายังมีอีกหลายระบบที่ใช้ UDP เช่น ระบบตั้งเวลา(NTP,SNTP), การดูข้อมูลสถานะของอุปกรณ์ต่างๆในระบบ(SNMP), การส่งไฟล์ (TFTP), การแปลงชื่อโดเมนเป็นหมายเลขไอพี (DNS), และอีก ฯลฯ เช่นกัน

ดังนั้น ถ้าเกิดระบบมีการป้องกันเฉพาะการใช้งาน TCP ทั้งหมด ซึ่งจะทำให้เข้าเว็บแบบปกติ (HTTP) และเข้าแบบ HTTPS ไม่ได้แล้ว  ก็หันมาใช้เข้าเว็บแบบ UDP ก็จะได้อยู่นะ ^_^

แต่ปัญหาหลักก็คือ... เว็บหรือบริการส่วนใหญ่ เขาจะเปิด server ที่รองรับไว้แต่ TCP นี่สิ  ให้เรายิงข้อมูล UDP ไปเท่าไหร่ ต่อให้มันทะลุผ่านการป้องกันไปหา server ได้โดยตรง แต่ server ไม่ได้รอรับข้อมูลที่ port นั้น ก็จะไม่ได้หยิบข้อมูลนั้นเอาไปประมวลผล มันก็ไร้ประโยชน์

ด้วยการนี้  เลยทำให้เราจำเป็นจะต้องมี proxy server ตัวกลางของเรา (อาจจะตั้งไว้ที่บ้าน หรือที่ทำงาน หรือที่อื่นๆ ที่สามารถต่อเน็ตได้ และได้ IP จริง) เพื่อทำการรอรับข้อมูลแบบ UDP จากเรา (ที่กำลังอยู่ใน wifi ที่ไม่มีล็อคอิน) แปลงข้อมูล แล้วนำไปทำการติดต่อกับ server ปลายทางด้วย TCP แบบที่ต้องการ  และเมื่อได้ข้อมูลจาก server ปลายทางแล้ว ตัวกลางตัวนี้ จะต้องทำหน้าที่แปลงข้อมูลนั้น ให้อยู่ในรูปแบบ UDP แล้วส่งกลับมาหาเราได้ด้วย

 .... ซึ่ง .... เริ่มยุ่งยากละ


จากรูป เวลาส่งข้อมูลไปหา server ปลายทางตามแนวคิดนี้จะส่งข้อมูลแบบนี้ ซึ่งจำเป็นอย่างมากที่เราจะต้องมี proxy server เป็นตัวกลางที่จะทำการแปลง UDP ไปเป็น TCP เพื่อติดต่อกับ server ปลายทาง และจะขากลับ ก็จะต้องแปลง TCP ไปเป็น UDP และส่งกลับไปเส้นทางเดิม

(หมายเหตุ วิธีนี้เรียกว่า "Tunneling" ซึ่งเปรียบได้กับการที่เราขุดอุโมงค์ต่อตรงไปหา proxy server ของเราเลย  โดยคนที่อยู่ระหว่างทางจะไม่สามารถดูข้อมูล หรือ แก้ไขข้อมูล ที่เราส่งไปหา proxy server ได้  แล้วเมื่อข้อมูลโผล่ออกจากอุโมงค์ที่ proxy server ก็จะวิ่งไปหา server ปลายทางได้ตามปกติ  ส่วนพอขากลับ ข้อมูลจาก serverปลายทาง ก็จะมุดลงอุโมงค์เดิม ย้อนกลับไปหาผู้ใช้งานได้)

ถ้าเราเลือกแล้วว่าเราจะอยากจะใช้ระบบแบบนี้  จะต้องทำยังไงบ้าง?

...ขอแนะนำ ให้ใช้การส่งข้อมูลแบบ DNS (UDP port 53)

เพราะว่า DNS ซึ่งเป็นระบบที่ใช้ในการแปลงชื่อโดเมน(เช่น google.com) ให้กลายเป็นหมายเลขไอพี(เช่น 113.21.241.24) เรียกได้ว่า เป็นระบบพื้นฐานสำหรับเน็ตเวิร์คที่ติดต่อไปหาอินเตอร์เน็ตได้จำเป็นต้องมี

ไม่เช่นนั้น คนที่เข้าเล่นอินเตอร์เน็ตจาก Wifi วงนั้นจะไม่สามารถเปิดเว็บต่างๆด้วยชื่อได้เลย  จำเป็นจะต้องกรอกด้วยไอพีอย่างเดียว ยกตัวอย่าง เช่น ถ้าต้องการเข้า Google.com แต่ว่าเราไม่มีระบบแปลง IP ให้ เลยจำเป็นต้องจำว่า google.com มี IP (ค่านึงจากหลายๆค่า) เป็น 113.21.241.24  และเวลาที่จะเข้า Google ก็จะต้องกรอก http://113.21.241.24 แต่ละครั้ง มันจะทรมาณแค่ไหน

ความน่าจะเป็นไปได้อีกอย่างคือ ในระบบการล็อคอินเข้าใช้เน็ตของ Wifi นั้น  บางทีหน้าที่ใช้ในการล็อคอิน  ก็ยังใช้ชื่อโดเมนที่จะต้องเอาไปแปลงเป็นไอพีก่อนถึงจะเปิดหน้านั้นได้

สรุปแล้ว จึงมีโอกาสสูง ที่ระบบ Wifi  จะ ไม่มีการบล็อคการใช้งาน DNS ในระบบ

ส่วนจะมีเครื่องมืออะไรบ้าง ขออ้างอิงจาก https://groups.google.com/forum/?fromgroups=#!topic/wimax-hacking/JYCdbsz7X0U ละกัน

โดยหลักๆ จะมี

ไม่ลงรายละเอียดละกันเดี๋ยวจะยาว  (จริงๆแค่นี้ก็ยาวมากละ)

3. ICMP


ICMP ย่อมาจาก Internet Control Message Protocol ซึ่งเป็น Protocol ที่แตกต่างกับ TCP และ UDP โดยที่มันอยู่คนละชั้นกันเลยกับ TCP และ UDP เมื่อเทียบกับ OSI model  โดยหน้าที่หลักของ ICMP คือเอาไว้ใช้ตรวจสอบการติดต่อกันของระบบเน็ตเวิร์ค  โดย ตัวอย่างที่เห็นกันบ่อยก็คือ การใช้คำสั่ง ping ที่เอาไว้เช็คว่าเครื่องปลายทางตอบสนองกลับมาช้าเร็วเท่าไหร่  ซึ่ง ping ก็ใช้ ICMP ในการทำงานด้วย

ดังนั้น ถ้าเราจะทำแบบเดิมที่ทำบน UDP แต่มาใช้ ICMP แทน ก็ทำได้เหมือนกัน  อาจจะดีกว่าด้วยตรงที่ว่า ICMP มีโอกาสที่ผู้ดูแลระบบจะไม่ได้บล็อคมากกว่า DNS (เนื่องจากผู้ดูแลระบบก็อาจจะใช้ ICMP เองด้วย เลยบล็อคไม่ได้)


ส่วนลิสต์ของโปรแกรมที่ใช้ทำ ICMP Tunnel (นำมาจาก http://en.wikipedia.org/wiki/ICMP_tunnel) ก็จะมี

สรุป

ในระบบอินเตอร์เน็ตไร้สาย ที่มีการตั้งค่าไว้ไม่ดีพอ อาจจะสามารถทำการ by-pass ออกไปสู่อินเตอร์เน็ตได้ในหลายช่องทาง  โดยสรุปคือ

  1. ติดต่อออกทาง TCP port เช่น ใช้ HTTPS ในการเปิดเข้าเว็บต่างๆ ที่ให้บริการแบบ HTTPS อยู่แล้ว
    • ข้อดี: ใช้งานง่าย, ไม่ต้องติดตั้งโปรแกรมเพิ่มเติม, เว็บไซต์ดังๆมักจะรองรับการใช้งานแบบ HTTPS อยู่แล้ว
    • ข้อเสีย: ไม่ใช่ทุกเว็บไซต์จะรองรับการเข้าแบบ HTTPS, ระบบ wifi มักจะป้องกันไ่ม่ให้เข้าถึงอินเตอร์เน็ตทาง TCP ทุก port
  2. ติดต่อออกทาง UDP port เช่น การใช้ DNS Tunneling เพื่อไปออกที่ proxy server ก่อน แล้วจึงให้ proxy server ทำการติดต่อแบบ TCP ไปหาเว็บปลายทางให้แทน
    • ข้อดี: ทะลุการป้องกันในระบบที่ห้ามใช้ TCP ทั้งหมดได้, DNS ค่อนข้างที่จะเป็นช่องทางที่มักเปิดไว้อยู่แล้วในระบบที่ออกเน็ตได้
    • ข้อเสีย: จำเป็นจะต้องมี proxy server ที่จะทำการแปลงไปกลับระหว่าง UDP และ TCP ให้ (ซึ่งส่วนใหญ่ proxy server ทั่วไปไม่เป็นแบบนี้), จะต้องมี public IP และ domain name ของ proxy server เครื่องนั้น, จะต้องทำการตั้งค่าหลายอย่างซึ่งทำให้ยุ่งยาก, ไม่สามารถใช้บนเครื่องผู้ใช้ได้ทันที จะต้องทำการติดตั้งโปรแกรมเพิ่มเติมก่อน
  3. ติดต่อออกทาง ICMP port
    • ข้อดี: ต่อให้ป้องกันทั้ง TCP และ UDP แต่มักจะไม่ป้องกันการใช้ ICMP เนื่องจากว่าผู้ดูแลระบบยังจำเป็นที่จะต้องใช้ ICMP ในเครื่องมือที่ใช้ดูแลระบบอยู่
    • ข้อเสีย: (เหมือนข้อเสียของ UDP ทุกอย่าง)


3/14/2013

MD5 กับ Hash Collision


วันนี้มีคนมาถามเรื่องว่า MD5 มีโอกาสเกิด Hash Collision เท่าไหร่

ขอเกริ่นย่อๆ สำหรับคนไม่รู้ว่าแต่ละตัวคืออะไรก่อนนะ

  • hash = วิธีการการย่อยข้อมูลเพื่อสร้างรหัสเฉพาะแต่ละข้อมูลออกมา เช่น file ไฟล์ๆนึงขนาดใหญ่มาก อาจจะคำนวนค่า hash ได้เหลือแค่ไม่กี่ bytes
  • MD5 = เป็นวิธีการคำนวนค่า hash วิธีหนึ่ง โดยผลลัพธ์ของ MD5 จะมีขนาด 128 bits หรือ 16 bytes
  • ส่วน Hash Collision (หรือเรียกอีกอย่างว่าปัญหา Birthday Attack) = รหัสเฉพาะข้อมูลที่สร้างขึ้นมา(hash)เนี่ย มันมีโอกาสที่จะซ้ำกันได้ 

ซึ่งความน่าจะเป็นนั้นเท่าไหร่มาดูกัน

เริ่มจาก..

สมมุติว่าตอนนี้มี Hash อยู่ในมือ k ตัว (k มีไม่กี่ตัว ซึ่ง k < N มากๆ)
ถ้าเราเอาแต่ละตัวมาจับเทียบกัน จะสามารถจับคู่ได้ทั้งหมด k*(k-1)/2 คู่
โดยมาจาก
  เราเลือกตัวซ้ายได้ k ตัว แต่พอจะเลือกตัวขวาที่จะมาจับคู่ด้วยจะเหลือเลือกได้แค่ k-1 ตัว(เพราะว่าตัวซ้ายโดนเลือกไปแล้วตัวนึง)
  และในการจับคู่กัน อาจจะเกิดการสลับที่กันได้ แบบ A-B, B-A ดังนั้นเพื่อลดปัญหาคู่เหมือนกันแต่สลับที่กัน เลยต้องหาร 2 ออก

จากจำนวนคู่ตรงนี้พักไว้ก่อน

ต่อมาลองมาคิดในภาพใหญ่ว่า...

ถ้าเกิด Hash จะชนกันได้ โอกาสมันจะเป็นเท่าไหร่
เนื่องจากถ้าเป็น MD5 ซึ่งมีผลลัพธ์ของ MD5 ออกมาขนาด 128 bits (16 bytes)
ดังนั้นจะสามารถสร้างค่า Hash ได้ไม่ซ้ำกันทั้งหมด
N = 2^128 = 340282366920938463463374607431768211456 = 3.4*10^38 ตัว
ดังนั้นถ้าเราเลือก Hash ออกมาซักคู่นึง โดยล๊อคค่าทางฝั่งซ้ายมือไว้ แล้วหวังว่าคู่ของมันจะมีโอกาสซ้ำเนี่ย
เนื่องจาก hash อีกตัวจะเป็นอะไรก็ได้ใน hash ทั้งหมดที่สามารถสร้างได้
ดังนั้น
ความน่าจะเป็นที่มันจะซ้ำกัน ก็คือ หยิบออกมา 1 ใน hash ทั้งหมดที่สร้างได้ ซึ่งก็คือ 1/N หรือ 1/2^128 = 2^-128
พอได้ความน่าจะเป็นที่มันจะซ้ำใน 1 คู่ใดๆแล้ว เราก็สามารถเอามาคำนวนความน่าจะเป็นเฉลี่ยได้ว่า

ในจำนวน hash k ตัวที่เรามีเนี่ย จะมีกี่ตัวที่ซ้ำ ด้วยการเอาไปคูณกับจำนวนคู่ที่เราคำนวนไว้ตอนแรก

ความน่าจะเป็นเฉลี่ยที่จะมี hash ชนกันในกลุ่ม hash จำนวน k ตัว จะมีค่า = จำนวนคู่ทั้งหมด * ความน่าจะเป็นที่จะเกิดการชนกันในแต่ละคู่
   λ = ( k(k-1)/2 ) * ( 1/N )
      = k(k-1)/2N

ณ จุดนี้ ถ้าหากใช้ Poisson Distribution เพื่อคำนวนหาความน่าจะเป็นที่จะเกิดการชนกัน
และเนื่องจากค่าเฉลี่ยของการเกิดเหตุการณ์ใดๆใน Poisson Distribution จะมีความน่าจะเป็น = E(X) = λ
เราสามารถย้อนกลับไปใช้ สูตรความน่าจะเป็นใดๆของ Poisson ได้ด้วยสูตร
 P(X=x) = (x^k * e^-λ)/x!
โดย x คือ จำนวนคู่ที่ hash เกิดการชนกัน
ถ้าต้องการความน่าจะเป็นที่ไม่เกิดการชนกันขึ้นเลย(x=0) จะได้ค่าเท่ากับ
 P(X=0) = (0^k * e^-λ)/0!
      = e^-λ
      = e^-(k(k-1)/2N)
และความน่าจะเป็นที่จะเกิดการชนกันขึ้นอย่างน้อย 1 ตัวขึ้นไป (x=1,2,3,..) จะมีค่าเท่ากับ
P(X=1,2,3...) = 1 - P(X=0) = 1 - e^-(k(k-1)/2N)
ซึ่งเมื่อแทนค่า N ซึ่งเป็นขนาด Hash ทั้งหมดที่สามารถสร้างได้ของ MD5 แล้ว (N=2^128) ก็จะได้สมการเป็น
P(X=1,2,3...) = 1 - e^-(k(k-1)/2^129)
ซึ่งจะสามารถ plot เป็นกราฟได้ดังรูป

http://www.wolframalpha.com/input/?i=1+-+e%5E-%28k%28k-1%29%2F2%5E129%29

ซึ่งจะเห็นได้ว่า  เมื่อเริ่มต้นที่เรามีจำนวนhash น้อยๆ (k ต่ำ)
โอกาสการชนกันของ hash ในมือจะต่ำมาก
และโอกาสการชนกันของ hash จะเริ่มเพิ่มขึ้นเรื่อยๆ เมื่อ k มีค่าสูงเพิ่มขึ้น

หรือหมายถึงว่า ยิ่งเรามี hash มากเท่าไหร่ ยิ่งได้เปอร์เซนต์ในการชนกันที่สูงขึ้น

ซึ่งโดยปกติแล้ว เขามักจะคิดว่าการเกิด hash collision จะอาการหนักมากๆ เมื่อมีความน่าจะเป็นในการเกิด collision > 50%

ถ้าเรานำค่านั้นมาแทนในสมการ เพื่อทำการหาค่า k จะได้ว่า
 P(ในการชน) = 50% = 0.5 = 1 - e^-(k(k-1)/2^129)
       e^-(k(k-1)/2^129) = 1-0.5 = 0.5
       -(k(k-1)/2^129) = ln(0.5)
       k(k-1)/2^129 = ln(0.5^-1) = ln(2)
       k(k-1) = 2^129 * ln(2)
ณ จุดนี้เพื่อความง่าย ขอประมาณค่า k(k-1)==>k^2 เมื่อ k มีค่ามากๆ
จะได้เป็น
       k^2 = 2^129(ln(2))
       k = sqrt(2^129(ln(2))) = sqrt(2)*2^64*sqrt(ln(2))
       k = 21,719,381,355,163,560,000 = 2.1719 * 10^19
ตามรูป
http://www.wolframalpha.com/input/?i=1+-+e%5E-%28k%28k-1%29%2F2%5E129%29+%3D+0.5



สรุป

MD5 ซึ่งมีผลลัพธ์ออกมาเป็นค่า 128 bits จะมีโอกาสเกิด Hash Collision มากๆ (50% ขึ้นไป) เมื่อมีจำนวน hash มากกว่า 2.1719 * 10^19 ตัวขึ้นไป หรือประมาณ 2^64.2 ตัวขึ้นไป

References:


ป.ล. 
ปัจจุบันมีคนหาวิธีทำให้เกิด MD5 Hash Collision ที่เร็วๆได้แล้ว ในระดับที่สร้างค่า hash ประมาณ 2^24.1 ตัวเท่านั้น ซึ่งสามารถทำเสร็จได้ภายในเวลาประมาณ 6 วินาที(ด้วย CPU 2.6 GHz)
อ้างอิงเพิ่ม