Gnark out-of-memory during deserialization with crafted inputs

Thanks @pventuzelo for reporting.

From the correspondence:

> Hi,
>
> We (Fuzzinglabs & Lambdaclass) found that during deserialization of certain files representing a VerifyingKey, an excessive memory allocation is happening consuming a lot of resources and even triggering a crash with the error fatal error: runtime: out of memory.
>
> Please find the details below:
>
> ## Vulnerability Details
>
> - Severity: Critical -> DoS
> - Affected Component: Deserialization
>
> ## Environment
>
> - Compiler Version: go version go1.22.2 linux/amd64
> - Distro Version: Ubuntu 24.04.1 LTS
>
> - Additional Environment Details:
> - [github.com/consensys/gnark](http://github.com/consensys/gnark) v0.11.0
> - [github.com/consensys/gnark-crypto](http://github.com/consensys/gnark-crypto) v0.14.1-0.20240909142611-e6b99e74cec1
>
> ## Steps to Reproduce
>
> You can download the needed files here: https://drive.google.com/drive/folders/1KQ5I3vv4bUllvqbatGappwbAkIcR2NI_?usp=sharing
>
> You have to run
>
> shell > go run gnark_poc.go >
>
> in a terminal.
>
> Running the provided code will result in a memory crash or an extremely large memory allocation, which can be observed using the following command:
>
> shell > go tool pprof -web mem.pprof >
>
> ## Root Cause Analysis
>
> The provided code loads a VerifyingKey from old.vk by calling the ReadFrom function. This function is implemented in backend/groth16/bn254/marshal.go within the gnark library.
>
> The provided example uses the elliptic curve BN-254, so the code resides in the backend/groth16/bn254/ repertory. However, the same error exists in other repertories, such as backend/groth16/bls12-377/.
>
> At line 207, a slice is allocated with a length of nbCommitments. This variable is directly extracted from the deserialized file, which, in our case, has a value of 2,327,186,600. This large value may be too big for some configurations, leading to memory allocations of approximately ±1 TB, as observed with pprof.
>
> ## Detailed Behavior
>
> shell > go run gnark_poc.go >
>
> > fatal error: runtime: out of memory > > runtime stack: > runtime.throw({0x5fe946?, 0x2052ae?}) > /usr/lib/go-1.22/src/runtime/panic.go:1023 +0x5c fp=0x7ffd65b321a0 sp=0x7ffd65b32170 pc=0x438a9c > runtime.sysMapOS(0xc000400000, 0x8ab6400000) > /usr/lib/go-1.22/src/runtime/mem_linux.go:167 +0x11b fp=0x7ffd65b321e0 sp=0x7ffd65b321a0 pc=0x418bbb > runtime.sysMap(0xc000400000, 0x8ab6400000, 0x7b19c8?) > /usr/lib/go-1.22/src/runtime/mem.go:155 +0x34 fp=0x7ffd65b32200 sp=0x7ffd65b321e0 pc=0x418634 > runtime.(*mheap).grow(0x7a17c0, 0x455b066?) > /usr/lib/go-1.22/src/runtime/mheap.go:1534 +0x236 fp=0x7ffd65b32270 sp=0x7ffd65b32200 pc=0x42b176 > runtime.(*mheap).allocSpan(0x7a17c0, 0x455b066, 0x0, 0x1) > /usr/lib/go-1.22/src/runtime/mheap.go:1246 +0x1b0 fp=0x7ffd65b32310 sp=0x7ffd65b32270 pc=0x42a850 > runtime.(*mheap).alloc.func1() > /usr/lib/go-1.22/src/runtime/mheap.go:964 +0x5c fp=0x7ffd65b32358 sp=0x7ffd65b32310 pc=0x42a2fc > runtime.systemstack(0x46d79f) > /usr/lib/go-1.22/src/runtime/asm_amd64.s:509 +0x4a fp=0x7ffd65b32368 sp=0x7ffd65b32358 pc=0x46912a > > goroutine 1 gp=0xc0000061c0 m=0 mp=0x798ca0 [running]: > runtime.systemstack_switch() > /usr/lib/go-1.22/src/runtime/asm_amd64.s:474 +0x8 fp=0xc000031b68 sp=0xc000031b58 pc=0x4690c8 > runtime.(*mheap).alloc(0x5bc040?, 0xc00012bb08?, 0xa0?) > /usr/lib/go-1.22/src/runtime/mheap.go:958 +0x5b fp=0xc000031bb0 sp=0xc000031b68 pc=0x42a25b > runtime.(*mcache).allocLarge(0xc000126510?, 0x8ab60ca800, 0x1) > /usr/lib/go-1.22/src/runtime/mcache.go:234 +0x87 fp=0xc000031c00 sp=0xc000031bb0 pc=0x4176e7 > runtime.mallocgc(0x8ab60ca800, 0x5d92a0, 0x1) > /usr/lib/go-1.22/src/runtime/malloc.go:1165 +0x597 fp=0xc000031c88 sp=0xc000031c00 pc=0x40ef97 > runtime.makeslice(0xc00011c180?, 0x0?, 0x2?) > /usr/lib/go-1.22/src/runtime/slice.go:107 +0x49 fp=0xc000031cb0 sp=0xc000031c88 pc=0x4500c9 > [github.com/consensys/gnark/backend/groth16/bn254.(*VerifyingKey).readFrom(0xc0001b7088](http://github.com/consensys/gnark/backend/groth16/bn254.(*VerifyingKey).readFrom(0xc0001b7088), {0x6598a0, 0xc00011dc50}, 0x0) > /home/raunan/go/pkg/mod/[github.com/!ronan!thoraval/[email protected]/backend/groth16/bn254/marshal.go:214](http://github.com/!ronan!thoraval/[email protected]/backend/groth16/bn254/marshal.go:214) +0x765 fp=0xc000031ea8 sp=0xc000031cb0 pc=0x59b205 > [github.com/consensys/gnark/backend/groth16/bn254.(*VerifyingKey).ReadFrom(0x100469020](http://github.com/consensys/gnark/backend/groth16/bn254.(*VerifyingKey).ReadFrom(0x100469020)?, {0x6598a0?, 0xc00011dc50?}) > /home/raunan/go/pkg/mod/[github.com/!ronan!thoraval/[email protected]/backend/groth16/bn254/marshal.go:166](http://github.com/!ronan!thoraval/[email protected]/backend/groth16/bn254/marshal.go:166) +0x1f fp=0xc000031ed8 sp=0xc000031ea8 pc=0x59aa5f > main.main() > /home/raunan/gnark_poc/gnark_poc/gnark_poc.go:19 +0xba fp=0xc000031f50 sp=0xc000031ed8 pc=0x5addda > runtime.main() > /usr/lib/go-1.22/src/runtime/proc.go:271 +0x29d fp=0xc000031fe0 sp=0xc000031f50 pc=0x43b55d > runtime.goexit({}) > /usr/lib/go-1.22/src/runtime/asm_amd64.s:1695 +0x1 fp=0xc000031fe8 sp=0xc000031fe0 pc=0x46b0e1 > > goroutine 2 gp=0xc000006c40 m=nil [force gc (idle)]: > runtime.gopark(0x0?, 0x0?, 0x0?, 0x0?, 0x0?) > /usr/lib/go-1.22/src/runtime/proc.go:402 +0xce fp=0xc000074fa8 sp=0xc000074f88 pc=0x43b98e > runtime.goparkunlock(...) > /usr/lib/go-1.22/src/runtime/proc.go:408 > runtime.forcegchelper() > /usr/lib/go-1.22/src/runtime/proc.go:326 +0xb3 fp=0xc000074fe0 sp=0xc000074fa8 pc=0x43b813 > runtime.goexit({}) > /usr/lib/go-1.22/src/runtime/asm_amd64.s:1695 +0x1 fp=0xc000074fe8 sp=0xc000074fe0 pc=0x46b0e1 > created by runtime.init.6 in goroutine 1 > /usr/lib/go-1.22/src/runtime/proc.go:314 +0x1a > > goroutine 3 gp=0xc000007180 m=nil [GC sweep wait]: > runtime.gopark(0x0?, 0x0?, 0x0?, 0x0?, 0x0?) > /usr/lib/go-1.22/src/runtime/proc.go:402 +0xce fp=0xc000075780 sp=0xc000075760 pc=0x43b98e > runtime.goparkunlock(...) > /usr/lib/go-1.22/src/runtime/proc.go:408 > runtime.bgsweep(0xc0000240e0) > /usr/lib/go-1.22/src/runtime/mgcsweep.go:278 +0x94 fp=0xc0000757c8 sp=0xc000075780 pc=0x426cf4 > runtime.gcenable.gowrap1() > /usr/lib/go-1.22/src/runtime/mgc.go:203 +0x25 fp=0xc0000757e0 sp=0xc0000757c8 pc=0x41b845 > runtime.goexit({}) > /usr/lib/go-1.22/src/runtime/asm_amd64.s:1695 +0x1 fp=0xc0000757e8 sp=0xc0000757e0 pc=0x46b0e1 > created by runtime.gcenable in goroutine 1 > /usr/lib/go-1.22/src/runtime/mgc.go:203 +0x66 > > goroutine 4 gp=0xc000007340 m=nil [GC scavenge wait]: > runtime.gopark(0xc0000240e0?, 0x657100?, 0x1?, 0x0?, 0xc000007340?) > /usr/lib/go-1.22/src/runtime/proc.go:402 +0xce fp=0xc000075f78 sp=0xc000075f58 pc=0x43b98e > runtime.goparkunlock(...) > /usr/lib/go-1.22/src/runtime/proc.go:408 > runtime.(*scavengerState).park(0x797520) > /usr/lib/go-1.22/src/runtime/mgcscavenge.go:425 +0x49 fp=0xc000075fa8 sp=0xc000075f78 pc=0x4246e9 > runtime.bgscavenge(0xc0000240e0) > /usr/lib/go-1.22/src/runtime/mgcscavenge.go:653 +0x3c fp=0xc000075fc8 sp=0xc000075fa8 pc=0x424c7c > runtime.gcenable.gowrap2() > /usr/lib/go-1.22/src/runtime/mgc.go:204 +0x25 fp=0xc000075fe0 sp=0xc000075fc8 pc=0x41b7e5 > runtime.goexit({}) > /usr/lib/go-1.22/src/runtime/asm_amd64.s:1695 +0x1 fp=0xc000075fe8 sp=0xc000075fe0 pc=0x46b0e1 > created by runtime.gcenable in goroutine 1 > /usr/lib/go-1.22/src/runtime/mgc.go:204 +0xa5 > > goroutine 18 gp=0xc000102700 m=nil [finalizer wait]: > runtime.gopark(0xc000074648?, 0x40f445?, 0xa8?, 0x1?, 0xc0000061c0?) > /usr/lib/go-1.22/src/runtime/proc.go:402 +0xce fp=0xc000074620 sp=0xc000074600 pc=0x43b98e > runtime.runfinq() > /usr/lib/go-1.22/src/runtime/mfinal.go:194 +0x107 fp=0xc0000747e0 sp=0xc000074620 pc=0x41a887 > runtime.goexit({}) > /usr/lib/go-1.22/src/runtime/asm_amd64.s:1695 +0x1 fp=0xc0000747e8 sp=0xc0000747e0 pc=0x46b0e1 > created by runtime.createfing in goroutine 1 > /usr/lib/go-1.22/src/runtime/mfinal.go:164 +0x3d > exit status 2 >
>
> ## Appendices
>
> This problem can also happen with ProvingKey.

Impact

Prover and verifier denial of service in case of maliciously crafted inputs (public key, verification key).

Patches

The issue is patched in https://github.com/Consensys/gnark/pull/1307. It was merged to gnark master at https://github.com/Consensys/gnark/commit/47ae846339add2bdf9983e499342bfdfe195191d. The fix will be incorporated in the next minor release of gnark (v0.11.1).

Workarounds

There are no convenient work-arounds currently. The best approach currently is to run key verification as a separate service which halts the verification pipeline in case of OOM when verification keys come from untrusted sources.