Đến nội dung

Hình ảnh

Thuật toán bảo mật SHA-1 bị chinh phục

- - - - -

  • Please log in to reply
Chủ đề này có 21 trả lời

#1
NangLuong

NangLuong

    Thành viên Diễn đàn Toán.

  • Hiệp sỹ
  • 2488 Bài viết
Như vậy là phương thức mã hóa được coi là chuẩn của việc bảo vệ các kênh liên lạc trực tuyến tồn tại 9 năm qua đã bị phá vỡ sau khi một nhóm 3 chuyên gia tại Đại học Shandong (Trung Quốc) phát hiện cách khai thác.

Việc một nền tảng mã hóa như vậy bị đục thủng là chuyện lớn. Theo đó, tất cả các ứng dụng và phần mềm server tích hợp SHA-1 (viết tắt của Secure Hash Algorithm) trong các chức năng như trình duyệt web, gửi/nhận e-mail, nhắn tin nhanh, bảo mật, mã hóa đĩa và file….sẽ cần phải được thay thế hoặc nâng cấp. ìĐây là một vấn đề nghiêm trọng trong công nghệ SHA. Chúng tôi biết điều này sẽ xảy ra nhưng không nghĩ lại sớm đến vậy”, Bruce Schneider, một nhà nghiên cứu về mã hóa, nhận xét trên trang web riêng.

Tuy nhiên, Schneider trấn an rằng, việc SHA-1 bị phá vỡ không có nghĩa là các kênh liên lạc mã hóa của bạn sẽ ngay lập tức bị theo dõi. Người sử dụng máy tính sẽ không bị tác động gì bất ngờ. Các kênh liên lạc trực tuyến chưa bị xé toang ngay vì vẫn còn một chuẩn bảo mật ìrắn” hơn chưa bị phá, gọi là SHA-256. Giới chuyên gia mã hóa đang thúc giục các công ty phần mềm tích hợp ngay SHA-256 vào các ứng dụng hiện còn dùng SHA-1. Jon. D. Callas, Giám đốc công nghệ hãng PGP, một công ty chuyên về giải pháp bảo mật máy tính cá nhân và doanh nghiệp, cho biết các sản phẩm sắp tới của họ sẽ tích hợp SHA-256. Phiên bản PGP 9 chuẩn bị được giới thiệu thử nghiệm beta trong vài tuần tới.

Thuật toán băm một chiều (hash) cho giá trị kết quả đầu ra có kích thước không đổi theo đầu vào trên nguyên tắc:
- Giá trị đầu ra là không đổi khi giữ nguyên vẹn giá trị đầu vào cho dù thuật toán được thực hiện vào bất cứ thời điểm nào. Thuật toán được sử dụng bất cứ khi nào.
- Sử dụng hàm băm một chiều, không thể tính toán ngược từ giá trị đầu ra để biết được giá trị đầu vào.
- Không thể tính toán hai đầu vào khác nhau để có cùng một giá trị hash khi thực hiện cùng một thuật toán băm.
Theo chuyên gia Schneider, SHA-1 là thuật toán ìbăm” một chiều (hash) dùng trong rất nhiều hệ thống như SSH, SSL, S/MIME, PGP, IPSec, VPNs…. Nó được Cơ quan an ninh quốc gia Mỹ phát minh năm 1995 và trở thành chuẩn bảo mật cơ sở phổ biến nhất trên Internet. Các nhân viên mật mã thường dùng công cụ này để tính những giá trị ìhash” ở mỗi thông điệp bí mật, từ đó đảm bảo rằng nội dung không bị xâm nhập trong quá trình truyền đi và không thể bị gián điệp chui vào làm thay đổi cấu trúc. ìHashing được biết đến ít hơn nhiều so với bất kỳ khía cạnh nào trong ngành mã hóa”, Giám đốc Callas của PGP nói. ìCó lẽ sẽ phải mất từ 2 đến 5 năm nữa chúng ta mới thực sự hiểu hết những thuật toán như thế này và trong thời gian đó sẽ có nhiều điều lớn hơn xảy ra”.

Việc phá mã bảo mật như SHA thường đòi hỏi một sức mạnh tính toán rất lớn. Các nhà nghiên cứu Trung Quốc khi c*rack SHA-1 đã không có nhiều siêu máy tính trong tay, nên thay vào đó, họ sử dụng một chương trình điện toán phân tán giống như dự án SETI@Home (setiathome.ssl.berkeley.edu) để khai thác sức mạnh nhàn rỗi của hàng nghìn máy tính trên thế giới và hoàn tất công việc. ìTrường hợp đột nhập đáng chú ý nhất từ trước đến nay vào các hệ thống mã hóa là vụ xuyên thủng chuẩn MD5-RC64 nhờ sức mạnh của 300.000 máy tính và phải mất 5 năm”, Callas cho biết. ìPhá SHA-1, khó hơn gấp 16 lần, cũng cần 300.000 máy tính nhưng phải mất xấp xỉ 74 năm”. Tuy nhiên, với việc tận dụng được sức mạnh liên kết của nhiều máy tính gia đình như các nhà khoa học Trung Quốc đã làm nói trên, thời gian thực hiện điều này đã được rút ngắn rất nhiều.

Theo vnexpress (Phan Khương)

#2
Polytopie

Polytopie

    Trung sĩ

  • Thành viên
  • 151 Bài viết
Có lẽ độ 20 năm nữa thì tất cả các dạng bảo mật hiện nay chỉ cần mất độ 1 giây đồng hồ để giải mã, và chỉ cần bằng 1 chiếc máy tính đặc biệt. :pi
Tôi tư duy nên Tôi không tồn tại.

#3
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết

Có lẽ độ 20 năm nữa thì tất cả các dạng bảo mật hiện nay chỉ cần mất độ 1 giây đồng hồ để giải mã, và chỉ cần bằng 1 chiếc máy tính đặc biệt. :D

20 năm nữa thì các thuật toán bảo mật "hiện nay" sẽ bị phá nhưng những thuật toán bảo mật "khi đó" vẫn sẽ khó mà bị phá.

#4
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết
Về việc phá mã các hàm băm MD5, SHA-0, SHA-1.

Tại hội nghị Crypto 04, Eli Biham (Israel, cựu hội trưởng hội mật mã) và Antoine Joux (Pháp)-hai người đứng đầu trong việc nghiên cứu việc phá các hàm băm có những phát hiện mới về việc phá các hàm băm. Những phát hiện này là rất "nhỏ giọt" (độ phức tạp của việc phá chỉ được cải thiện nho nhỏ thôi) và việc tìm đụng độ đối với SHA-0 chỉ là "near collision" (tức tìm ra hai đầu vào để giá trị hàm băm trên đó là gần giống nhau). Đột nhiên, trong phiên họp không chính thức (Rump Session), một nữ khoa học Trung Quốc Xiaoyun Wang tuyên bố rằng nhóm của cô đã phá được một loạt các hàm băm MD4,MD5,..., và cả SHA-0. Do ở phiên không chính thức, mỗi bài chỉ được nói trong 4 phút nên đó là một tuyên bố chẫn động nhưng chưa được kiểm chứng.

Ba tháng sau, tại cuộc họp mời (4 năm một lần, gồm 50 chuyên gia đứng đầu giới mật mã trong 4 năm, các bài phát biểu trong 1 tiếng về những thành tựu mới nhất của họ và chưa được đăng) của giới mật mã diễn ra tại Luminy-Marseille (Pháp), nữ tiến sỹ Trung Quốc (người trước đó hoàn toàn vô danh trong giới mật mã) được mời đến phát biểu. Bài phát biểu của cô về phá hàm băm SHA-0 không làm ai hiểu. Không phải vì khó hiểu mà do cô đã trình bày không rõ ràng và do cô chưa từng thực tập tiếng Anh nên mọi người không hiểu cô đang nói tiếng Anh hay "Trung Quốc". Tât cả các câu hỏi của những vị tổ sư như Adi Shamir, Biham,Joux...đều bị cô bỏ qua. Trước tình thế đó, Eli Biham đã có một nghĩa cử cao đẹp. Ông gặo riêng Xiaoyun và tìm hiểu mọi vấn đề. Sau đó, Eli quyết định mở riêng một phiên họp ngoại lệ vào buổi đêm để giải thích các kết quả của nhóm TQ. Phiên họp diễn ra từ 9h tối đến 1h đêm đã sáng tỏ nhiều vấn đề và độ tin cậy của thuật toán được nâng lên rất cao.

Sau 5 tháng làm việc của hội đồng chọn bài của hội nghị Eurocrypt 05, cuối tháng 1 vừa qua, kết quả đã được chấp nhận trình bày ở hội nghị chính thức Eurocrypt 05 này (một trong ba hội nghị chính thức hàng năm của tổ chức Mật mã thế giới bên cạnh Crypto và AsiaCrypt) nơi tất cả các kết quả sẽ được đăng. Đáng kể hơn, kết quả về việc phá hàm băm SHA-0 và các hàm băm khác (trừ SHA-1) được chọn là Best Paper của hội nghị.

Thế nhưng chưa hết, ngay sau khi bài báo được chấp nhận. Nhóm TQ này lại đưa ra phương pháp phá mã đối với hàm băm SHA-1. Chũng ta hãy đợi sự kiểm chứng của các nhà mật mã học trong thời gian tới, nhưng theo nhiều chuyên gia, kết quả có lẽ là đúng.

Ảnh hưởng của việc phá mã hàm băm SHA-1:
- Về mặt lý thuyết: tất cả các chứng minh bảo mật sử dụng hàm băm SHA-1 đều không còn đúng.

-Về mặt thực tế thì hiện tại chưa có gì nguy hại lắm. Hàm băm được sử dụng cơ bản trong Chữ ký điện tử . Nôm na, thay vì ký trên một văn bản M dài loằng ngoằng, người ta sẽ ký trên giá trị hàm băm H(M) của nó (H() có đọ dài cố định; chẳng hạn 160 bít trong SHA-1). Nếu hàm băm là collision-free, nghĩa là không tài nào tìm được hai giá trị M1,M2 để H(M1) = H(M2), việc ký trên M hay trên H(M) là như nhau vì ta có thể coi H(M) là duy nhất. Nhưng nay, việc tìm ra collision, tức là tìm được M1,M2 để H(M1) = H(M2), do đó chữ ký trên văn bản M1 cũng là chữ ký trên văn bản M2. Do vậy, kẻ gian có thể dùng chữ ký một người trên M1 để làm chữ ký người đó trên văn bản M2 -> Nguy hiểm.
RC nói răng về mặt thực tế, kết quả tìm Collision không quá nguy hiểm là bởi người ta mới chỉ tìm được các giá trị M1, M2 đặc biệt mà thôi. Các giá trị này thường là những chuỗi ký tự lung tung, vô nghĩa và do vậy: thứ nhất, không ai lại đi ký trên một văn bản vô nghĩa M1 cả; thứ hai, dù có ai ngố đi ký trên văn bản M1 thì việc giả mạo chữ ký trên một văn bản vô nghĩa M2 khác chẳng đem lại điều gì lớn lao.

Vấn đề sẽ nghiêm trọng hơn nếu giải quyêt được bài toán "second pre-image". Tức là cho trước M, H(M); tìm M' để H(M)= H(M'). Tức là kẻ gian không được quyền chọn 2 văn bản mà một trong hai văn bản đã được định trước (là một văn bản thật trong thực tế). Khi đó, nếu một người đã ký trên một văn bản thông thường M, kẻ gian có thể lợi dụng để giả mạo chữ ký trên một văn bản M' khác.

#5
nemo

nemo

    Hoa Anh Thảo

  • Founder
  • 416 Bài viết
Nói thêm về thuật toán băm một chiều (thuật toán one-way-hash). Với tất cả những ai quan tâm tới bảo mật đều biết one-way-hash là một thuật toán bảo mật thông dụng và an toàn nhất hiện nay (Trong WinNT file SAM cũng được mã hóa dựa trên nền của thuật toán Hash).

SHA được liệt vào một trong các giải thuật mã hóa bất đối xứng. Giải thuật trình bày hai khái niệm đó chính là public và private key, tính an toàn và độ phức tạp của giải thuật chính là nhờ phép toán liên quan đến tích số của một cặp số nguyên tố rất lớn, tạo ra một số cực lớn mà hầu như không thể đoán ngược trở lại được hai số nguyên tố ban đầu. Mã hóa bất đối xứng ra đời để giúp cho việc trao đổi "chìa khóa bí mật" - secret keys được dễ dàng hơn nó khắc phục được những nhược điểm của giải thuật mã hóa đối xứng là nó không cho biết được tính xác thực cũng như sự toàn vẹn của data, nó cũng bất tiện ở chỗ là secret key để mã và giải mã data cần phải được trao đổi riêng qua các phương tiện khác (out of band) chứ không thể gởi đi cùng data được mặc dù nó nhanh hơn thuật toán bất đối xứng tới cả ngàn lần.

Với các data có độ dài khác nhau bất kỳ khi được cho qua một thuật toán one-way-hash thì sẽ được "băm" ra thành các chuỗi có chiều dài khá nhỏ và cố định như nhau được gọi là message digest (ví dụ: b90c9054849c187aa681464bb62b9a95, 16cb26421451cc406f5bc111b969c38f) và thuật toán này bảo đảm rằng nếu nội dung data bị thay đổi (dù chỉ là một bit) thì kết quả của message digest cũng sẽ thay đổi, các giải thuật hash dùng 128-bit key: MD2, MD4, MD5, 160 bit-key: SHA, SHA-1... đây chính là yếu tố then chốt để kiểm tra tính toàn vẹn của dữ liệu, lý do tại sao lại phải cần có message digest có chiều dài khá nhỏ như vậy là ở chỗ:

Giả sử bạn nhận được một message email với nội dung như ví dụ ở trên và nội dung của message sẽ được cho qua một thuật toán one-way-hash MD5 chẳng hạn, kết quả là ta có một message digest tương ứng, sau đó người gửi sẽ lấy PRIVATE key của mình để ký (mã hóa) vào message digest đó để tạo thành một cái gọi là DIGITAL SIGNATURE, và chữ ký điện tử này sẽ được gởi kèm theo message ban đầu đến bạn.

Khi nhận được email từ người gửi bạn sẽ lấy PUBLIC key của người gửi để giải mã DIGITAL SIGNATURE và có được message digest của người gửi, so sánh kết quả này và giá trị tính toán MD5 lại nội dung message ngay tại máy của bạn nếu chúng giống nhau thì có nghĩa là message không bị thay đổi (đơn giản quá phải không các bạn) vì chỉ có người gửi là người giữ PRIVATE key dùng để "ký", và nếu message digest mà có chiều dài quá lớn thì thời gian để mã và giải mã các message digest này rất lâu và cũng tốn nhiều băng thông (bandwidth) để gởi thêm "chữ ký" này đi nữa.
<span style='color:purple'>Cây nghiêng không sợ chết đứng !</span>

#6
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết

SHA được liệt vào một trong các giải thuật mã hóa bất đối xứng. Giải thuật trình bày hai khái niệm đó chính là public và private key, tính an toàn và độ phức tạp của giải thuật chính là nhờ phép toán liên quan đến tích số của một cặp số nguyên tố rất lớn, tạo ra một số cực lớn mà hầu như không thể đoán ngược trở lại được hai số nguyên tố ban đầu. Mã hóa bất đối xứng ra đời để giúp cho việc trao đổi "chìa khóa bí mật" - secret keys được dễ dàng hơn nó khắc phục được những nhược điểm của giải thuật mã hóa đối xứng là nó không cho biết được tính xác thực cũng như sự toàn vẹn của data, nó cũng bất tiện ở chỗ là secret key để mã và giải mã data cần phải được trao đổi riêng qua các phương tiện khác (out of band) chứ không thể gởi đi cùng data được mặc dù nó nhanh hơn thuật toán bất đối xứng tới cả ngàn lần.

Hi nemo,
SHA là Secure Hash Algorithm, tức là hàm băm chứ không phải là asymmetric encryption. Do vậy trong SHA chẳng có khóa công khai, bí mật gì cả. SHA-1 là cải tiến của SHA-0, SHA-0 cũng chỉ là cải tiến của MD5, MD4.

Do hàm băm là một hàm công khai (không có khóa gì cả), ai cũng có thể áp dụng nó nên không thể đúng khi nói "Với tất cả những ai quan tâm tới bảo mật đều biết one-way-hash là một thuật toán bảo mật thông dụng và an toàn nhất hiện nay".

#7
queensland

queensland

    Hạ sĩ

  • Thành viên
  • 97 Bài viết

SHA là Secure Hash Algorithm, tức là hàm băm chứ không phải là asymmetric encryption. Do vậy trong SHA chẳng có khóa công khai, bí mật gì cả. SHA-1 là cải tiến của SHA-0, SHA-0 cũng chỉ là cải tiến của MD5, MD4.

Đúng thế. Và SHA-1 cũng như các tiền thân của nó, chẳng dùng số nguyên tố lớn nào cả.

Vấn đề sẽ nghiêm trọng hơn nếu giải quyêt được bài toán "second image". Tức là cho trước M, H(M); tìm M' để H(M)= H(M'). Tức là kẻ gian không được quyền chọn 2 văn bản mà một trong hai văn bản đã được định trước (là một văn bản thật trong thực tế). Khi đó, nếu một người đã ký trên một văn bản thông thường M, kẻ gian có thể lợi dụng để giả mạo chữ ký trên một văn bản M' khác.

Cũng chưa nghiêm trọng lắm bởi vì cũng như M, M' nếu đáng để kẻ gian lợi dụng cũng phải là một văn bản có nghĩa. Việc tạo ra một văn bản vừa có nghĩa, vừa đáng lợi dụng và đồng thời có cùng image với một văn bản có nghĩa khác là khó khăn không thể tả.

Một ứng dụng tưởng chừng có thể bị đe dọa bởi trường hợp "second image" là xác thực bằng mật khẩu, trong đó hệ thống lưu trữ giá trị hash của mật khẩu và các mật khẩu là chuỗi ký tự ngẫu nhiên chứ không nhất thiết phải có nghĩa. Tuy thế, ngay cả ứng dụng này cũng không bị đe dọa lắm: trong những thuật toán hash như SHA, văn bản trước khi hash được nối dài thêm bởi một chuỗi số phụ thuộc nội dung văn bản (việc này gọi là padding). Như vậy, ngay cả trong ứng dụng xác thực bằng mật khẩu, M, M' vẫn có một độ dư nhất định, tức là vẫn "có nghĩa". Các tác giả Trung Quốc không xử lý được padding trong phương pháp tấn công của mình.

#8
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết
Hi queensland,

Vấn đề sẽ nghiêm trọng hơn nếu giải quyêt được bài toán "second image". Tức là cho trước M, H(M); tìm M' để H(M)= H(M'). Tức là kẻ gian không được quyền chọn 2 văn bản mà một trong hai văn bản đã được định trước (là một văn bản thật trong thực tế). Khi đó, nếu một người đã ký trên một văn bản thông thường M, kẻ gian có thể lợi dụng để giả mạo chữ ký trên một văn bản M' khác.

Cũng chưa nghiêm trọng lắm bởi vì cũng như M, M' nếu đáng để kẻ gian lợi dụng cũng phải là một văn bản có nghĩa. Việc tạo ra một văn bản vừa có nghĩa, vừa đáng lợi dụng và đồng thời có cùng image với một văn bản có nghĩa khác là khó khăn không thể tả.

Co thể ta chưa thấy nghiêm trọng ngay nhưng có độ "nghiêm trọng tiềm ẩn" cao. Các phương pháp tìm đụng độ thường là biến đổi chút ít đầu vào ở một số vị trí, giá trị đặc biệt để đầu ra vẫn được giữ nguyên. Do vậy nếu văn bản M chứa nội dung rất dài nhưng có một chỗ "tôi ko giết ông ta" mà kẻ gian lại đổi chỉ chữ "ko" thành chữ "có" và giữ nguyên toàn bộ phần còn lại thì rất rất nguy hiểm đấy chứ!

Các tác giả Trung Quốc không xử lý được padding trong phương pháp tấn công của mình.

ĐÚng vậy nhưng cũng là điều dễ hiểu. Các nhà phá má TQ không giải quyết bài toán "second image" mà là tìm ra "collision". Do vậy các bản rõ M1,M2 là hoàn toàn đặc biệt theo sự chọn lựa của họ, và ví thế tất nhiên không có định dạng thỏa mãn theo một qui tắc "padding" nào cả.
Tuy nhiên, một phương pháp tìm "second pre-image" tốt hoàn toàn "có thể" giải quyết vấn đề "padding".

#9
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết
Tho^ng tin the^m : Phuong phap pha ma cac ham bam cua cac nha mat ma hoc Trung Quoc (Best paper cua hoi nghi) se duoc trinh bay trong phien khai mac cua hoi nghi Eurocrypt 2005-hoi nghi chinh thuc cua Hoi mat ma the gioi.
http://www.brics.dk/...05/program.html

#10
asterixvn

asterixvn

    Lính mới

  • Thành viên
  • 1 Bài viết
Sau hội nghị EuroCrypt'05, RC nhớ có bài tường thuật để anh em cập nhật thêm thông tin nhé.

#11
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết
Tin nhanh trực tiếp của phóng viên diễn đàn toán học tại hội nghị Eurocrypt vừa khai mạc tại Aarhus-Đan Mạch.

Buổi đón tiếp mào đầu của hội nghị đã diễn ra rất đông vui và vừa mới kết thúc cách đây 10 phút. Hơn 500 người tham gia gồm hầu như tất cả các nhà khoa học trong lĩnh vực, rất nhiều những người trong quân đội cũng tham dự, và không ít những người đứng đầu các công ty lớn cũng đến tìm hiểu.

Ngày mai, sau gần 1 năm tuyên bố các kết quả chấn động liên quan đến việc phá một loạt các hàm băm MD4, MD5, RIPEMD, SHA0, SHA1, các nhà Trung Quốc sẽ lần đầu tiên chính thức trình bày một phần các kết quả của mình tại phiên khai mạc hội nghị! Các kết quả này được trình bày cũng đã đồng nghĩa với việc hội đồng thẩm định (gồm 31 nhà khoa học, làm việc trong khoảng 3 tháng) của hội nghị đã đánh giá độ chính xác của các kết quả đó. Tuy vậy, dù sao nó cũng đánh dấu một mốc khá quan trọng khi có lẽ là lần đầu tiên độ bảo mật của một chuẩn mật mã do NIST (National Institute of Standards and Technology) phê chuẩn bị lung lay!

Tuy vậy nhiều người cho rằng có nhiều bài trình bày khác cũng có tầm quan trọng không hề thua kém. Bài trình bày của Brent Water về thuật toán hiệu quả với việc dùng danh tính làm khóa công khai cũng rất được chú ý, bởi lẽ thuật toán của Water cho độ an toàn trong mô hình chuẩn không cần sử dụng các máy tư vấn ngẫu nhiên. (Efficient Identity-Based Encryption Without Random Oracles)

Chương trình của hội nghị trong đường dẫn dưới đây. Cùng Crypto (và dưới hơn 1 bậc là Asiacrypt), Eurocrypt trình bày các kết quả thú vị nhất của mật mã trong năm. Do vậy, nếu có ai cần tìm hiểu đến bài báo nào, phóng viên của diễn đàn sẽ chú ý tường thuật bài đó.
http://www.brics.dk/...05/program.html
Phóng viên DDTH.

PS: Diễn đàn hy vọng thỉnh thoảng nếu có dịp sẽ có thể tường thuật các hội nghị lớn trong năm liên quan đến các lĩnh vực khác nhau của Toán/Tin. Do đó, nếu có thành viên nào có thể tham gia nhiệm vụ tường thuật, cả làng luôn ủng hộ và hoan nghênh!

#12
queensland

queensland

    Hạ sĩ

  • Thành viên
  • 97 Bài viết
Hấp dẫn quá. Queensland rất háo hức mong chờ lời tường thuật về việc phá các hàm hash (của nhóm Trung Quốc và một số tác giả khác như Biham, Joux, Schneier) và báo cáo về IBE của Brent Water. Xin cảm ơn bác RongChơi nhiều.

Bài viết đã được chỉnh sửa nội dung bởi queensland: 24-05-2005 - 01:20


#13
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết
Sáng nay, bài trình bày của Xiaoyun Wang đã khai mạc hội nghị...

Trong buổi đón tiếp của thị trưởng thành phố tối nay, phóng viên DDTH đã có cuộc trao đổi trò chuyện với Xiaoyun Wang. Sau đây là tóm tắt 1 số ý trong cuộc nói chuyện vui đó ...

PVDDTH (gọi tắt là DD) Hi, xin chúc mừng cô về bài phát biểu sáng nay...
XW: Anh có thấy nó sáng sủa hơn là hồi ở Luminy ko?
(Chú thích: Cách đây nửa năm, tại một hội nghị không chính thức ở Luminy, Marseille Pháp, Xiaoyun Wang đã trình bày các kết quả của mình nhưng ... không ai hiểu vì cô nói tiếng Anh không tốt và vì các slides ngập đầy số liệu không ai thấy gì cả. Sau đó, Eli Biham và Antoaine Joux đã giúp cô rất nhiều trong việc làm người khác hiểu ý tưởng của mình).
DD: Sáng sủa hơn nhiều, các sildes sáng sủa và dể hiểu hơn nhiều :D
XW: (Cười) cảm ơn, đây là lần đầu tiên tôi phát biểu ở 1 trong 3 hội nghị của Mật Mã, và lại phát biểu đầu tiên nên cũng hồi hộp
DD: Và thật tuyêt là ở hội nghị Crypto sắp tới cô sẽ lại trình bày bài báo về phá hàm băm SHA-1.
XW: Tôi sẽ chuẩn bị rât nhiều để phát biểu (Cười tươi ...)
DD: Đối với hàm băm MD4, cô đã chỉ ra việc tìm collision dễ đến mức có thể tính bằng tay, chắc Ron Rivest (người xây dựng MD4, cũng là chữ R trong hệ RSA nổi tiếng) sẽ phải lắc đầu. Tuy nhiên, đối với SHA1, hình như cô chưa thể đưa ra collision thực sự mà chỉ mới là chứng minh về mặt lý thuyết?
XW: Yes, đúng là chưa thể tìm ra collision cụ thể. Độ phức tạp cao quá (2^69) vần ngoài tầm với của các máy tính hiện nay ...
DD: Sau bài báo ở Crypto, sẽ là một kết quả chấn động khác, chẳng hạn với bài toán tìm seconde preimage?
XW: Ồ, hiện tại thì tôi chưa nghì thêm gì cả, bài toán seconde preimage thì chắc là ... còn lâu, cái này khó lắm (Cười...).
DD: Cô có thể nói 1 chút về tình hình nghiên cứu ở Trung Quốc được không? Mà làm thế nào cô tới dự EuroCrypt thế nhỉ, chính phủ cấp chi phí cho cô hay là trường Đại học?
XW: Ồ, cách đây 10 năm thì quả là có khó khăn đấy, nhưng giờ đây mọi chuyện đã khác rồi. Trường tôi có chi phí dành cho nghiên cứu, có cả những nguồn tài chính thông qua các project nữa nên nếu tôi có bài báo ở hội nghị quốc tế thì sẽ không gặp khó khăn trong việc đi trình bày. (Cô chỉ sang một học trò đang làm PhD, và cũng là 1 trong các đồng tác giả của cô) anh thấy đấy, các học trò cũng được cấp chi phí để tham gia hội nghị ngay cả khi không trình bày.
DD: Cô có nghĩ là chúng ta sẽ có thể có những hợp tác trong tương lai trong khu vực không nhỉ, chẳng hạn vài năm nữa khi tôi về VN và mời cô sang giảng bài 1 tuần ý?
XW: Ồ, TQ với VN rất gần nhau, tôi cũng rất muốn trao đổi và chắc chắn là sẵn sàng sang VN rồi, nhưng nói tiếng Anh thì ... mệt lắm, tôi giảng 1 buổi bằng tiếng Anh nhé, 5 buổi còn lại bằng tiếng TQ được ko ( cười ). Ngoài ra thì cũng có thể trao đổi sinh viên giữa hai bên nữa chứ. Tôi hiện có 3 sinh viên làm PhD...
DD: Chúng ta phải kiếm cái gì đó đánh chén đi thôi, không có đói bụng mất :D

-------------

Trong ngày đầu tiên, không phải những bài báo đã nổi tiếng của Xiaoyun Wang, Brent Water, Boyen gây ấn tượng mà bài phát biểu của Tauman Kalai (từ MIT) đã để lại dấu ấn hơn cả. Sử dụng Smooth Projective Hashing (khái niêm này đại loại là: với 1 hàm h, nếu có khóa k thì luôn tình được h(k,x), tuy vậy nếu có hình chiếu A(k) thì chỉ có thể tính h(k,x) chỉ với những x trong một ngôn ngữ L nào đó) để xây dựng một primitive rất được quan tâm trong mật mã là Oblivious Transfer (đại loại là : tôi có một n dữ liêu, anh muốn mua của tôi 1 trong n dữ liệu đó mà sao cho: tôi thì không biết anh yêu cầu dữ liệu nào, còn anh thì lấy được đúng dữ liệu mình muốn nhưng không biết chút gì về n-1 dữ liệu còn lại). Cách xây dựng đẹp và bất ngờ...

PVDD

#14
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết
Đây là hình ảnh cô Xiaoyun Wang trình bày tại hội nghị

Hình gửi kèm

  • IMG_0287.JPG


#15
queensland

queensland

    Hạ sĩ

  • Thành viên
  • 97 Bài viết
Xiaoyun Wang et al. đã công bố collision SHA-1 (not SHA-0) với số vòng hạn chế từ vài tháng trước. Tại sao họ chưa công bố phương pháp của mình ngay trong hội nghị này nhỉ? Hay là chờ phá xong full SHA-1 (80 vòng) để kiểm chứng thời gian 2^69 cho chắc chắn?

#16
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết

Xiaoyun Wang et al. đã công bố collision SHA-1 (not SHA-0) với số vòng hạn chế từ vài tháng trước. Tại sao họ chưa công bố phương pháp của mình ngay trong hội nghị này nhỉ? Hay là chờ phá xong full SHA-1 (80 vòng) để kiểm chứng thời gian 2^69 cho chắc chắn?

Từ lúc công bố đến lúc được hội đồng kiểm chứng là một khoảng thời gian dài chứ? không phải công bố là trình bày chính thức ngay được. Tại Crypto, Xiaoyun Wang sẽ trình bày bài :

FINDING COLLISIONS IN THE FULL SHA1
Xiaoyun Wang and Yiqun Lisa Yin and Hongbo Yu

PS: Cũng may là trong crypto các kết quả đều được trình bày tại hội nghị chứ không như trong Toán, các kết quả đợi đăng báo thì chắc phải hơn năm trời bài mới được đăng ấy chứ.

#17
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết
cuoc hop hom nay ket thuc...

Hình gửi kèm

  • IMG_0058.JPG


#18
bellrus

bellrus

    Lính mới

  • Thành viên
  • 2 Bài viết
Chào các bạn.Rất hân hạnh được làm quen với tất cả mọi người.Mình xin tự giới thiệu một chút. Hiện tại mình đang học ngành mật mã ở trường tổng hợp Mat-cơ-va mang tên Lô-mô-nô-sốp.Mình cũng chỉ năm thứ 3 thôi, cho nên cũng chưa đi sâu như các bạn được. Vậy nên rất mong đựoc sự trao đổi và học hỏi từ các bạn.

Hiện tại thì mình rất quan tâm tới vấn đề :Cryptanalysis nói chung. Cho nên nếu bạn nào có tài liệu gì thì chỉ cho mình.
Nghe nói trong số các bạn cũng có người đi tham dự EUROCRYPT 2005 ? Nếu bạn có tất cả những bài báo liên quan tới Cryptanalysis thì gửi cho mình nhé. Rất cảm ơn các bạn.

#19
madness

madness

    Trung sĩ

  • Thành viên
  • 137 Bài viết

PS: Cũng may là trong crypto các kết quả đều được trình bày tại hội nghị chứ không như trong Toán, các kết quả đợi đăng báo thì chắc phải hơn năm trời bài mới được đăng ấy chứ.

Anh RongChoi được đi nhiều hội nghị, thích nhỉ :wub:

Hì hì, nói ngoài đề một tí. Có thể trong tin học người ta thường cố gắng "beat" nhau về độ hiệu quả về thời gian và tài nguyên (bộ nhớ) để giải quyết một bài. Vì thế nên người ta tranh nhau công bố kết quả sớm, vì nếu trước đó một người ra thuật toán O(n^2), sau đó A ra O(n^1.5), B ra (n log n), nếu A công bố trước B thì vẫn được công bố, nhưng nếu sau thì ko được; còn trong toán thì ko cần beat nhau như thế. Đó là lý do vì sao các bài báo trong tin được xuất bản nhanh hơn toán.

Một lý do khác nữa có thể là tin học phát triển nhanh hơn, có nhiều bài toán mới xuất hiện hơn trong thời gian ngắn hơn, mà việc giải quyết các bài đó ko đến nỗi khó như các bài toán kinh điển trong toán, vì thế trong tin học thường có nhiều kết quả được công bố hơn.

Đương nhiên, việc làm thế thì sẽ có những mặt tốt xấu riêng.

Có một câu hỏi, ko biết có ai có thể trả lời giúp ko ạ? Có nhiều từ để nói về một hội nghị khoa học, (về Maths hay Computer Science): conference, symposium, workshop, colloquium, congress. 3 từ đầu thường gặp trong Computer Science, ví dụ về từ thứ 5: International Congress of Mathematicians. Ko biết có ai giải thích giùm những loại hội nghị này khác nhau thế nào về độ lớn (tầm cỡ), hoặc về tiêu chuẩn các paper được chấp nhận ko ạ?

#20
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết

Chào các bạn.Rất hân hạnh được làm quen với tất cả mọi người.Mình xin tự giới thiệu một chút. Hiện tại mình đang học ngành mật mã ở trường tổng hợp Mat-cơ-va mang tên Lô-mô-nô-sốp.Mình cũng chỉ năm thứ 3 thôi, cho nên cũng chưa đi sâu như các bạn được. Vậy nên rất mong đựoc sự trao đổi và học hỏi từ các bạn.

Hiện tại thì mình rất quan tâm tới vấn đề :Cryptanalysis nói chung. Cho nên nếu bạn nào có tài liệu gì thì chỉ cho mình.
Nghe nói trong số các bạn cũng có người đi tham dự EUROCRYPT 2005 ? Nếu bạn có tất cả những bài báo liên quan tới Cryptanalysis thì gửi cho mình nhé. Rất cảm ơn các bạn.

Chào Bellrus,
Rất vui vì biết thêm 1 người cùng chung sở thích. Xin lỗi vì hôm nay RC mới vào đây trả lời được.

Nhánh Cryptanalysis quả là rất rắn nhưng cũng rộng vô biên. Thực ra hiện nay giữa Cryptography và Cryptanalysis đã có một cây cầu bắc qua. Trước đây thì 1 anh đề xuất hệ mã, anh khác nghĩ cách phá. Nay thì mọi việc đã thay đổi nhiều nhiều với sự ra đời của một nhánh mới : Provable Security. Khi đề xuất một hệ mã thì nhiều khi ta phải ìchứng minh” luôn rằng không thể có kẻ định nào có thể phá được hệ mã đó hoặc phải phân tích độ an toàn của hệ mã đó có thể đứng vững trước những kẻ tấn công nào. Đó là nói nôm na, nói chính xác hơn thì là, với một kẻ địch có sức mạnh thế này thế kia, thì không thể phá được hệ mã của tôi theo nghĩa này nghĩa nọ, dưới một giả thiết cụ thể (chẳng hạn bài toán factorization là khó). Do vậy, nói chung không có sự phân định rạch ròi giữa 1 bài báo thuộc Cryptography hay Cryptanalysis lắm. RC làm ở trong nhánh Provable Security này và ở Eurocrypt vừa rồi cũng được nhận và trình bày 1 bài trong đó có cả attack và cả construction,… Tóm lại là RC không biết phân biệt (trừ một số trường hợp) là bài nào thuộc Cryptanalysis để gửi cho bạn.

Hiện nay người ta ít khi nói răng mình làm về Cryptography hay Cryptanalysis chung chung mà thường nói mình làm về mảng nào : public-key encryption, digital signature, broadcast encryption, key exchange, … trong mỗi mảng lớn thì lại có nhánh con,… và trong bất cứ nhánh con nào cũng có cả phần thuộc Cryptography và phần thuộc Cryptanalysis.

Nếu Bellrus nói cụ thể hơn mình quan tâm đến nhánh nào và nếu nhánh đó RC có biết thì RC sẽ cố tìm và gửi tới Bellrus những bài báo quan trọng.

Cheers,
RC.




1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh