## LLL lattice basis reduction algorithm

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.Random` in the Minecraft server, then works backwards from that to locate other players currently loaded into the world.

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

## PuTTY 使用 ecdsa-sha2-nistp521 的漏洞

DSA 類的簽名演算法有個得很小心的地方，是 nonce 選擇不當會造成 key recovery，這在原文有提到：

All DSA signature schemes require a random value to be invented during signing, known as the 'nonce' (cryptography jargon for a value used only once), or sometimes by the letter k. It's well known that if an attacker can guess the value of k you used, or find any two signatures you generated with the same k, then they can immediately recover your private key.

With DSA, the entropy, secrecy, and uniqueness of the random signature value {\displaystyle k} are critical. It is so critical that violating any one of those three requirements can reveal the entire private key to an attacker. Using the same value twice (even while keeping {\displaystyle k} secret), using a predictable value, or leaking even a few bits of {\displaystyle k} in each of several signatures, is enough to reveal the private key {\displaystyle x}.

PuTTY's technique worked by making a SHA-512 hash, and then reducing it mod q, where q is the order of the group used in the DSA system. For integer DSA (for which PuTTY's technique was originally developed), q is about 160 bits; for elliptic-curve DSA (which came later) it has about the same number of bits as the curve modulus, so 256 or 384 or 521 bits for the NIST curves.

In all of those cases except P521, the bias introduced by reducing a 512-bit number mod q is negligible. But in the case of P521, where q has 521 bits (i.e. more than 512), reducing a 512-bit number mod q has no effect at all – you get a value of k whose top 9 bits are always zero.

This bias is sufficient to allow a key recovery attack. It's less immediate than if an attacker knows all of k, but it turns out that if k has a biased distribution in this way, it's possible to aggregate information from multiple signatures and recover the private key eventually. Apparently the number of signatures required is around 60.

To fix this vulnerability, we've completely abandoned PuTTY's old system for generating k, and switched to the RFC 6979 technique, for all DSA and ECDSA key types. (EdDSA keys such as Ed25519 already used a different system, which has not changed.) However, this doesn't affect the fact that information about existing P521 private keys has already been leaked whenever a signature was generated using the old k generator.

## NIST P-curve 的 Seed Bounty Program

Filippo Valsorda 發起了 seed bounty program，針對 NIST P-curve 裡 seed 的部分尋找 SHA-1 的 pre-image：「Announcing the \$12k NIST Elliptic Curves Seeds Bounty」。

```3045AE6FC8422F64ED579528D38120EAE12196D5
BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
C49D360886E704936A6678E1139D26B7819F7E90
A335926AA319A27A1D00896A6773A4827ACDAC73
D09E8800291CB85396CC6717393284AAA0DA64BA```

$y^2 = x^3 + ax + b (Weierstrass form)$ $y^2 = x^3 + ax^2 + bx (Montgomery form)$

$y^2 = x^3 + 486662x^2 + x$

To protect against various attacks discussed in Section 3, I rejected choices of A whose curve and twist orders were not {4 · prime, 8 · prime}; here 4, 8 are minimal since p ∈ 1+4Z. The smallest positive choices for A are 358990, 464586, and 486662. I rejected A = 358990 because one of its primes is slightly smaller than 2^252, raising the question of how standards and implementations should handle the theoretical possibility of a user’s secret key matching the prime; discussing this question is more difficult than switching to another A. I rejected 464586 for the same reason. So I ended up with A = 486662.

```3045AE6FC8422F64ED579528D38120EAE12196D5 # NIST P-192, ANSI prime192v1
BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5 # NIST P-224
C49D360886E704936A6678E1139D26B7819F7E90 # NIST P-256, ANSI prime256v1
A335926AA319A27A1D00896A6773A4827ACDAC73 # NIST P-384
D09E8800291CB85396CC6717393284AAA0DA64BA # NIST P-521```

Apparently, they were provided by the NSA, and generated by Jerry Solinas in 1997. He allegedly generated them by hashing, presumably with SHA-1, some English sentences that he later forgot.

[Jerry] told me that he used a seed that was something like:
SEED = SHA1("Jerry deserves a raise.")
After he did the work, his machine was replaced or upgraded, and the actual phrase that he used was lost. When the controversy first came up, Jerry tried every phrase that he could think of that was similar to this, but none matched.

## CloudFront 支援 3072 bit RSA 憑證

2048 bit 在一般情況算是夠用，畢竟現在的紀錄也才到 829 bit (參考「RSA Factoring Challenge」)：

1024-bit RSA keys are equivalent in strength to 80-bit symmetric keys, 2048-bit RSA keys to 112-bit symmetric keys, 3072-bit RSA keys to 128-bit symmetric keys, and 15360-bit RSA keys to 256-bit symmetric keys. In 2003, RSA Security claimed that 1024-bit keys were likely to become crackable some time between 2006 and 2010, while 2048-bit keys are sufficient until 2030. As of 2020 the largest RSA key publicly known to be cracked is RSA-250 with 829 bits.

## SHA-256 的 Length extension attack

Hacker News 上看到「Breaking SHA256: length extension attacks in practice (kerkour.com)」，在講不當使用 SHA-256 會導致 Length extension attack 類的安全漏洞，主要是因為 MD5SHA-1 以及 SHA-2 類的 hash function 最後生出 hash 值時會暴露出 hash function 的內部狀態而導致的問題。

```// Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message do
// ...

// Add this chunk's hash to result so far:
a0 := a0 + A
b0 := b0 + B
c0 := c0 + C
d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 // (Output is in little-endian)```

```Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99```

`Desired New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege`

```New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x28&waffle=liege
New Signature: 0e41270260895979317fff3898ab85668953aaa2```

## Post-Quantum 的 KEM，SIDH/SIKE 確認死亡

Ran on a single core, the appended Magma code breaks the Microsoft SIKE challenges \$IKEp182 and \$IKEp217 in about 4 minutes and 6 minutes, respectively.

A run on the SIKEp434 parameters, previously believed to meet NIST’s quantum security level 1, took about 62 minutes, again on a single core.

We also ran the code on random instances of SIKEp503 (level 2), SIKEp610 (level 3) and SIKEp751 (level 5), which took about 2h19m, 8h15m and 20h37m, respectively.

Ars Technica 的採訪「Post-quantum encryption contender is taken out by single-core PC and 1 hour」裡面，有問到 SIKE 的共同發明人 David Jao 的看法，他主要是認為密碼學界的人對於數學界的「武器」了解程度不夠而導致這次的情況：

It's true that the attack uses mathematics which was published in the 1990s and 2000s. In a sense, the attack doesn't require new mathematics; it could have been noticed at any time. One unexpected facet of the attack is that it uses genus 2 curves to attack elliptic curves (which are genus 1 curves). A connection between the two types of curves is quite unexpected. To give an example illustrating what I mean, for decades people have been trying to attack regular elliptic curve cryptography, including some who have tried using approaches based on genus 2 curves. None of these attempts has succeeded. So for this attempt to succeed in the realm of isogenies is an unexpected development.

In general there is a lot of deep mathematics which has been published in the mathematical literature but which is not well understood by cryptographers. I lump myself into the category of those many researchers who work in cryptography but do not understand as much mathematics as we really should. So sometimes all it takes is someone who recognizes the applicability of existing theoretical math to these new cryptosystems. That is what happened here.

## NIST 選出了四個 Post-Quantum Cryptography 演算法

NIST (NSA) 選出了四個 Post-quantum cryptography 演算法 (可以抵抗量子電腦的演算法)：「NIST Announces First Four Quantum-Resistant Cryptographic Algorithms」。

• CRYSTALS-Kyber：非對稱加密。
• CRYSTALS-Dilithium：數位簽名。
• FALCON：數位簽名。
• SPHINCS+：數位簽名。

## Amazon SES 總算支援 2048 bits RSA key 了

Amazon SES 總算是支援 2048 bits RSA key 了：「Amazon SES now supports 2048-bit DKIM keys」。

Until now, Amazon SES supported a DKIM key length of 1024-bit, which is the current industry standard.

KPM 的 Web 版使用了 `Math.random()`，在各家瀏覽器主要是用 xorshift128+ 實做 `Math.random()`，作者沒有針對這塊再花時間研究，但很明顯的 `Math.random()` 不是個 CSPRNG：

The underlying PRNG used by Chrome, Firefox and Safari for Math.random() is xorshift128+. It is very fast, but not suitable to generate cryptographic material. The security consequences in KPM has not been studied, but we advised Kaspersky to replace it with window.crypto.getRandomValues(), as recommended by the Mozilla documentation page previously mentioned.

Note: Math.random() does not provide cryptographically secure random numbers. Do not use them for anything related to security. Use the Web Crypto API instead, and more precisely the window.crypto.getRandomValues() method.

So the seed used to generate every password is the current system time, in seconds. It means every instance of Kaspersky Password Manager in the world will generate the exact same password at a given second.

The consequences are obviously bad: every password could be bruteforced. For example, there are 315619200 seconds between 2010 and 2021, so KPM could generate at most 315619200 passwords for a given charset. Bruteforcing them takes a few minutes.

Hacker News 上有不少陰謀論的討論，像是：

Getting some DUAL_EC prng vibes.

Insert Kaspersky owned by Russia intelligence conspiracy here...

## Intel 的 RDRAND 爆炸...

The random number generator is compliant with security and cryptographic standards such as NIST SP 800-90A, FIPS 140-2, and ANSI X9.82.

As explained in the earlier article, mitigating CrossTalk involves locking the entire memory bus before updating the staging buffer and unlocking it after the contents have been cleared. This locking and serialization now involved for those instructions is very brutal on the performance, but thankfully most real-world workloads shouldn't be making too much use of these instructions.

We disclosed an initial PoC (Proof-Of-Concept) showing the leakage of staging buffer content in September 2018, followed by a PoC implementing cross-core RDRAND/RDSEED leakage in July 2019. Following our reports, Intel acknowledged the vulnerabilities, rewarded CrossTalk with the Intel Bug Bounty (Side Channel) Program, and attributed the disclosure to our team with no other independent finders. Intel also requested an embargo until May 2020 (later extended), due to the difficulty of implementing a fix for the cross-core vulnerabilities identified in this paper.