LLL lattice basis reduction algorithm
source link: https://blog.gslin.org/archives/2024/04/23/11752/lll-lattice-basis-reduction-algorithm/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LLL lattice basis reduction algorithm
短短幾天內看到兩個不同的地方用到了 1982 年發現的「Lenstra–Lenstra–Lovász lattice basis reduction algorithm」。
第一個是「Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG (github.com/spawnmason)」這篇，作者群利用 LLL 去分析 java.util.Random 的內部狀態，進而得到其他玩家的地點資訊：
Every time a block is broken in Minecraft versions Beta 1.8 through 1.12.2, the precise coordinates of the dropped item can reveal another player's location.
"Randar" is an exploit for Minecraft which uses LLL lattice reduction to crack the internal state of an incorrectly reused
java.util.Randomin the Minecraft server, then works backwards from that to locate other players currently loaded into the world.
另外一個是在 Hacker News 上面的 id=40080651 提到，前幾天 PuTTY 的 p521 問題在底層也用到了 LLL：
LLL lattice reduction is the same algorithm that can be used for cracking PuTTY keys from biased nonces from the CVE a few days ago. 'tptacek explained a bit about the attack (and links to a cryptopals problem for it, which I can almost pretend to understand if I squint) https://news.ycombinator.com/item?id=40045377
從維基百科的內容也可以看出來 application 非常多，不光是密碼學的領域用到，看起來值得花點力氣來了解...
Related
所以要開始開發 CECPQ2 了...
CECPQ1 是 Google 在研究對抗量子電腦的演算法，作為測試用的演算法，曾經在 Google Chrome 的 54 beta 版 (2016 年) 存活過一段時間，最近又開始在開發新一代的演算法 CECPQ2 了，這次會是基於 TLS 1.3 上測試：「CECPQ2」。 CECPQ2 will be moving slowly: It depends on TLS 1.3 and, as mentioned, 1.3 is taking a while. The larger messages may take some time to deploy if we hit middlebox- or…
December 14, 2018In "Browser"
Google 與 Cloudflare 測試 Post-Quantum 演算法的成果
這幾年量子電腦的進展不斷有突破，雖然到對於攻擊現有的密碼學看起來還有一段時間，但總是得先開始研究對量子電腦有抵抗性的演算法... 其中 Google Chrome 的團隊與 Cloudflare 的團隊手上都有夠大的產品，兩個團隊合作測試的結果在學界與業界都還蠻重視的：「Real-world measurements of structured-lattices and supersingular isogenies in TLS」、「The TLS Post-Quantum Experiment」。 Google Chrome 這邊是使用了 Canary 與 Dev 兩個 channel，有控制組與兩個新的演算法： Google Chrome installs, on Dev and Canary channels, and on all platforms except iOS, were randomly assigned to one of three groups: control (30%),…
November 2, 2019In "Browser"
SSL broken *NOW*
Update：Mozilla 與 Micorosft 都發出 security report 了，參考 MD5 Weaknesses Could Lead to Certificate Forgery (Mozilla) 與 Microsoft Security Advisory (961509) Research proves feasibility of collision attacks against MD5。 標題的 NOW 有兩個意思，一個是強調「已經」，另外一個是「現在」。 在 2004 與 2005 年的時候，密碼學界相當轟動的事情：王小雲的 MD5 collision。這件事情很有名，但實際上更具破壞性的是 Arjen Lenstra、王小雲、Benne de Weger 三位所發表的「Colliding X.509 Certificates」，示範如何使用 MD5 collision 湊出一個合法的 X.509 certificate。…
December 31, 2008In "Browser"
Leave a Reply
Your email address will not be published. Required fields are marked *
Comment *
Name *
Email *
Website
Notify me of follow-up comments by email.
Notify me of new posts by email.
To respond on your own website, enter the URL of your response which should contain a link to this post's permalink URL. Your response will then appear (possibly after moderation) on this page. Want to update or remove your response? Update or delete your post and re-enter your post's URL again. (Learn More)
Post navigation
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK