This enables v8_enable_seeded_array_index_hash and add a test for it. Fixes: https://hackerone.com/reports/3511792 deps: V8: backport 0a8b1cdcc8b2 Original commit message: implement rapidhash secret generation Bug: 409717082 Change-Id: I471f33d66de32002f744aeba534c1d34f71e27d2 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/6733490 Reviewed-by: Leszek Swirski <leszeks@chromium.org> Commit-Queue: snek <snek@chromium.org> Cr-Commit-Position: refs/heads/main@{#101499} Refs:0a8b1cdcc8Co-authored-by: Joyee Cheung <joyeec9h3@gmail.com> deps: V8: backport 185f0fe09b72 Original commit message: [numbers] Refactor HashSeed as a lightweight view over ByteArray Instead of copying the seed and secrets into a struct with value fields, HashSeed now stores a pointer pointing either into the read-only ByteArray, or the static default seed for off-heap HashSeed::Default() calls. The underlying storage is always 8-byte aligned so we can cast it directly into a struct. Change-Id: I5896a7f2ae24296eb4c80b757a5d90ac70a34866 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7609720 Reviewed-by: Leszek Swirski <leszeks@chromium.org> Commit-Queue: Joyee Cheung <joyee@igalia.com> Cr-Commit-Position: refs/heads/main@{#105531} Refs:185f0fe09bCo-authored-by: Joyee Cheung <joyeec9h3@gmail.com> deps: V8: backport 1361b2a49d02 Original commit message: [strings] improve array index hash distribution Previously, the hashes stored in a Name's raw_hash_field for decimal numeric strings (potential array indices) consist of the literal integer value along with the length of the string. This means consecutive numeric strings can have consecutive hash values, which can lead to O(n^2) probing for insertion in the worst case when e.g. a non-numeric string happen to land in the these buckets. This patch adds a build-time flag v8_enable_seeded_array_index_hash that scrambles the 24-bit array-index value stored in a Name's raw_hash_field to improve the distribution. x ^= x >> kShift; x = (x * m1) & kMask; // round 1 x ^= x >> kShift; x = (x * m2) & kMask; // round 2 x ^= x >> kShift; // finalize To decode, apply the same steps with the modular inverses of m1 and m2 in reverse order. x ^= x >> kShift; x = (x * m2_inv) & kMask; // round 1 x ^= x >> kShift; x = (x * m1_inv) & kMask; // round 2 x ^= x >> kShift; // finalize where kShift = kArrayIndexValueBits / 2, kMask = kArrayIndexValueMask, m1, m2 (both odd) are the lower bits of the rapidhash secrets, m1_inv, m2_inv (modular inverses) are precomputed modular inverse of m1 and m2. The pre-computed values are appended to the hash_seed ByteArray in ReadOnlyRoots and accessed in generated code to reduce overhead. In call sites that don't already have access to the seeds, we read them from the current isolate group/isolate's read only roots. To consolidate the code that encode/decode these hashes, this patch adds MakeArrayIndexHash/DecodeArrayIndexFromHashField in C++ and CSA that perform seeding/unseeding if enabled, and updates places where encoding/decoding of array index is needed to use them. Bug: 477515021 Change-Id: I350afe511951a54c4378396538152cc56565fd55 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7564330 Reviewed-by: Leszek Swirski <leszeks@chromium.org> Commit-Queue: Joyee Cheung <joyee@igalia.com> Cr-Commit-Position: refs/heads/main@{#105596} Refs:1361b2a49dCo-authored-by: Joyee Cheung <joyeec9h3@gmail.com> deps: V8: cherry-pick aac14dd95e5b Original commit message: [string] add 3rd round to seeded array index hash Since we already have 3 derived secrets, and arithmetics are relatively cheap, add a 3rd round to the xorshift-multiply seeding scheme. This brings the bias from ~3.4 to ~0.4. Bug: 477515021 Change-Id: I1ef48954bcee8768d8c90db06ac8adb02f06cebf Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7655117 Reviewed-by: Chengzhong Wu <cwu631@bloomberg.net> Commit-Queue: Joyee Cheung <joyee@igalia.com> Reviewed-by: Leszek Swirski <leszeks@chromium.org> Cr-Commit-Position: refs/heads/main@{#105824} Refs:aac14dd95ePR-URL: https://github.com/nodejs-private/node-private/pull/834 CVE-ID: CVE-2026-21717 deps: V8: backport 185f0fe09b72 Original commit message: [numbers] Refactor HashSeed as a lightweight view over ByteArray Instead of copying the seed and secrets into a struct with value fields, HashSeed now stores a pointer pointing either into the read-only ByteArray, or the static default seed for off-heap HashSeed::Default() calls. The underlying storage is always 8-byte aligned so we can cast it directly into a struct. Change-Id: I5896a7f2ae24296eb4c80b757a5d90ac70a34866 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7609720 Reviewed-by: Leszek Swirski <leszeks@chromium.org> Commit-Queue: Joyee Cheung <joyee@igalia.com> Cr-Commit-Position: refs/heads/main@{#105531} Refs:185f0fe09bCo-authored-by: Joyee Cheung <joyeec9h3@gmail.com> deps: V8: backport 1361b2a49d02 Original commit message: [strings] improve array index hash distribution Previously, the hashes stored in a Name's raw_hash_field for decimal numeric strings (potential array indices) consist of the literal integer value along with the length of the string. This means consecutive numeric strings can have consecutive hash values, which can lead to O(n^2) probing for insertion in the worst case when e.g. a non-numeric string happen to land in the these buckets. This patch adds a build-time flag v8_enable_seeded_array_index_hash that scrambles the 24-bit array-index value stored in a Name's raw_hash_field to improve the distribution. x ^= x >> kShift; x = (x * m1) & kMask; // round 1 x ^= x >> kShift; x = (x * m2) & kMask; // round 2 x ^= x >> kShift; // finalize To decode, apply the same steps with the modular inverses of m1 and m2 in reverse order. x ^= x >> kShift; x = (x * m2_inv) & kMask; // round 1 x ^= x >> kShift; x = (x * m1_inv) & kMask; // round 2 x ^= x >> kShift; // finalize where kShift = kArrayIndexValueBits / 2, kMask = kArrayIndexValueMask, m1, m2 (both odd) are the lower bits of the rapidhash secrets, m1_inv, m2_inv (modular inverses) are precomputed modular inverse of m1 and m2. The pre-computed values are appended to the hash_seed ByteArray in ReadOnlyRoots and accessed in generated code to reduce overhead. In call sites that don't already have access to the seeds, we read them from the current isolate group/isolate's read only roots. To consolidate the code that encode/decode these hashes, this patch adds MakeArrayIndexHash/DecodeArrayIndexFromHashField in C++ and CSA that perform seeding/unseeding if enabled, and updates places where encoding/decoding of array index is needed to use them. Bug: 477515021 Change-Id: I350afe511951a54c4378396538152cc56565fd55 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7564330 Reviewed-by: Leszek Swirski <leszeks@chromium.org> Commit-Queue: Joyee Cheung <joyee@igalia.com> Cr-Commit-Position: refs/heads/main@{#105596} Refs:1361b2a49dCo-authored-by: Joyee Cheung <joyeec9h3@gmail.com> deps: V8: cherry-pick aac14dd95e5b Original commit message: [string] add 3rd round to seeded array index hash Since we already have 3 derived secrets, and arithmetics are relatively cheap, add a 3rd round to the xorshift-multiply seeding scheme. This brings the bias from ~3.4 to ~0.4. Bug: 477515021 Change-Id: I1ef48954bcee8768d8c90db06ac8adb02f06cebf Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7655117 Reviewed-by: Chengzhong Wu <cwu631@bloomberg.net> Commit-Queue: Joyee Cheung <joyee@igalia.com> Reviewed-by: Leszek Swirski <leszeks@chromium.org> Cr-Commit-Position: refs/heads/main@{#105824} Refs:aac14dd95e
27 lines
531 B
JavaScript
27 lines
531 B
JavaScript
'use strict';
|
|
|
|
// See https://hackerone.com/reports/3511792
|
|
|
|
const payload = [];
|
|
const val = 1234;
|
|
const MOD = 2 ** 19;
|
|
const CHN = 2 ** 17;
|
|
const REP = 2 ** 17;
|
|
|
|
if (process.argv[2] === 'benign') {
|
|
for (let i = 0; i < CHN + REP; i++) {
|
|
payload.push(`${val + i}`);
|
|
}
|
|
} else {
|
|
let j = val + MOD;
|
|
for (let i = 1; i < CHN; i++) {
|
|
payload.push(`${j}`);
|
|
j = (j + i) % MOD;
|
|
}
|
|
for (let k = 0; k < REP; k++) {
|
|
payload.push(`${val}`);
|
|
}
|
|
}
|
|
|
|
const string = JSON.stringify({ data: payload });
|
|
JSON.parse(string);
|