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.

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```

Hashcat 在 3090 與 4090 上的速度差異

```Hashmode: 3200 - bcrypt \$2*\$, Blowfish (Unix) (Iterations: 32)
Speed.#1.........:    96662 H/s (36.29ms) @ Accel:8 Loops:16 Thr:11 Vec:1```
```* Hash-Mode 3200 (bcrypt \$2*\$, Blowfish (Unix)) [Iterations: 32]
Speed.#1.........:   184.0 kH/s (50.22ms) @ Accel:4 Loops:32 Thr:24 Vec:1```

```Hashmode: 8900 - scrypt (Iterations: 1)
Speed.#1.........:  2308.2 kH/s (8.64ms) @ Accel:16 Loops:1 Thr:16 Vec:1```
```* Hash-Mode 8900 (scrypt) [Iterations: 16384]
Speed.#1.........:     7126 H/s (29.16ms) @ Accel:128 Loops:1024 Thr:32 Vec:1```

```Hashmode: 9300 - Cisco-IOS \$9\$ (scrypt) (Iterations: 1)
Speed.#1.........:    85331 H/s (122.39ms) @ Accel:16 Loops:1 Thr:8 Vec:1```
```* Hash-Mode 9300 (Cisco-IOS \$9\$ (scrypt)) [Iterations: 16384]
Speed.#1.........:    83890 H/s (1.76ms) @ Accel:128 Loops:1024 Thr:32 Vec:1```

```Hashmode: 9200 - Cisco-IOS \$8\$ (PBKDF2-SHA256) (Iterations: 19999)
Speed.#1.........:   187.2 kH/s (91.61ms) @ Accel:16 Loops:256 Thr:1024 Vec:1```
```* Hash-Mode 9200 (Cisco-IOS \$8\$ (PBKDF2-SHA256)) [Iterations: 19999]
Speed.#1.........:   430.1 kH/s (60.71ms) @ Accel:16 Loops:512 Thr:512 Vec:1```

```Hashmode: 10900 - PBKDF2-HMAC-SHA256 (Iterations: 999)
Speed.#1.........:  3785.4 kH/s (87.58ms) @ Accel:4 Loops:999 Thr:1024 Vec:1```
```* Hash-Mode 10900 (PBKDF2-HMAC-SHA256) [Iterations: 999]
Speed.#1.........:  8865.7 kH/s (50.50ms) @ Accel:64 Loops:124 Thr:512 Vec:1```

Content Defined Chunking (CDC)

Google 的人看起來像是是在 CI/CD 階段遇到頻寬上的問題 (從「The builds are 40-45 GB large.」這邊猜)，用 scprsync 看起來都不能解，所以他們自己刻了 FastCDC 演算法來解。

`0123456789abcdef 0123456789abcdef 0123456789abcdef 0123456789abcdef`

`0123456789abcdef 0123456789ABCDEF 0123456789abcdef 0123456789abcdef`

`ABC0123456789abc def0123456789abc def0123456789abc def0123456789abc def`

For each fingerprint, restic then tests if the lowest 21 bits are zero. If this is the case, restic found a new chunk boundary.

Git 在 SHA-256 支援上遇到的問題

Bjarmason pointed out that there is still no interoperability between SHA-1 and SHA-256 repositories, and that none of the Git hosting providers appear to be supporting SHA-256.

Git是一種源代碼管理系統，它使用散列函數將每個對象（例如文件的每個版本）和每個提交都轉換為一個數值，用於存儲該對象。散列函數的安全性是整個倉庫完整性的重要組成部分。如果攻擊者可以用具有相同散列值的另一個提交替換提交，他們可能會在不冒檢測風險的情況下將惡意代碼植入倉庫中。這種前景令任何依賴 Git 倉庫中代碼安全性的人感到擔心，也就是所有人。

Git 項目早已選擇 SHA-256 作為 SHA-1 的替代品。Git 最初是使用 SHA-1 寫成的，但是這些代碼已被重構，並且可以處理多種散列類型，其中 SHA-256 是第二種支持的類型。現在可以使用 SHA-256 創建 Git 倉庫（只需使用 --object-format=sha256 標誌），大多數本地操作都會正常工作。Git 中支持替代散列算法的基礎是2020年發布的2.29版本的一部分，並且似乎很穩定。

NIST 更新了 SHA-1 的淘汰計畫

NISTSHA-1 的新的淘汰計畫出來了：「NIST Retires SHA-1 Cryptographic Algorithm」。

The results presented so far on SHA-1 do not call its security into question. However, due to advances in technology, NIST plans to phase out of SHA-1 in favor of the larger and stronger hash functions (SHA-224, SHA-256, SHA-384 and SHA-512) by 2010.

As today’s increasingly powerful computers are able to attack the algorithm, NIST is announcing that SHA-1 should be phased out by Dec. 31, 2030, in favor of the more secure SHA-2 and SHA-3 groups of algorithms.

“Modules that still use SHA-1 after 2030 will not be permitted for purchase by the federal government,” Celi said.

在圖片裡面放入圖片本身的 MD5 值

Hacker News Daily 上看到「The image in this post displays its own MD5 hash (retr0.id)」這篇，作者想要產生一張 PNG 圖，這張圖的 MD5 值就在圖片上呈現。然後作者本人有出現在 Hacker News 討論串上面，提到流量撐不住，所以丟到 Twitter 上面 (而很幸運的，Twitter 沒有壓這張圖，是保留原圖，所以可以驗證 MD5)：

SHA-1 在 2022 的破解速度已經降到 ~5.4 GPU years

Remarkably, we can see that in only 5 years, we're down from an attack costing ~110 GPU years to an attack costing ~8 GPU-years in 2020 (thanks to theoretical improvements & newer GPUs) to just ~5.4 GPU years nowadays (thanks to newer, faster GPUs).

In a more realistic way, it would take less than a day to do it on a super-computer such as the one owned by the US Department of Energy's Oak Ridge National Laboratory (ORNL) named "Summit".

Amazon S3 支援 MD5 以外的檢查演算法了

Amazon S3 宣佈支援 MD5 以外的檢查演算法了：「New – Additional Checksum Algorithms for Amazon S3」。

In particular, you can specify the use of any one of four widely used checksum algorithms (SHA-1, SHA-256, CRC-32, and CRC-32C) when you upload each of your objects to S3.

The four additional checksums are now available in all commercial AWS Regions and you can start using them today at no extra charge.

GTA 的啟動讀取效能問題

```struct {
uint64_t *hash;
item_t   *item;
} entry;```

But before it’s stored? It checks the entire array, one by one, comparing the hash of the item to see if it’s in the list or not. With ~63k entries that’s (n^2+n)/2 = (63000^2+63000)/2 = 1984531500 checks if my math is right. Most of them useless. You have unique hashes why not use a hash map.

• hook strlen
• wait for a long string
• “cache” the start and length of it
• if it’s called again within the string’s range, return cached value

And as for the hash-array problem, it’s more straightforward - just skip the duplicate checks entirely and insert the items directly since we know the values are unique.

JdeBP 3 days ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300.

There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not.

The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far.