Segmentation fault on -m 94 -m 95

[floyd-fuh]

So I've run fuzzing tests with American Fuzzy Lop (AFL, http://lcamtuf.coredump.cx/afl/ ), as argon2 takes all it's arguments from command line I used the argv fuzzer included in AFL (in experimental/argv_fuzzing/argv-fuzz-inl.h).

There are only two changes necessary to make argon2 fuzzable by AFL:

1. include the argv-fuzz-inl.h header file in main.c.
2. add as first line in the main function in main.c: AFL_INIT_SET0("argon2");

This means argon2 will read arguments from stdin as zero byte delimited values. See argv-fuzz-inl.h for details. You need to produce test corpus data first (input files where AFL can start from). I only started with one file "test" (where \x00 are zero bytes):

r\x00-y\x00i\x00-t\x004\x00-m\x003\x00-l\x004\x00-p\x003\x00-i\x00lalalal\x00\x00

To see if it that test file is correctly working with (reading zero byte delimited values from stdin):

$ cat input/test | ./argon2-afl/argon2 
Argon2i with
        t_cost = 4
        m_cost = 8
        password = lalalal
        salt = 00000000000000000000000000000000
0.011 seconds (74.406 mebicycles)
745182e43ac2b9a26584e100e1c98db657b3775a561a6de9abc5305bc9f7abef
$argon2i$m=8,t=4,p=4$AAAAAAAAAAAAAAAAAAAAAA$dFGC5DrCuaJlhOEA4cmNtlezd1pWGm3pq8UwW8n3q+8

Then AFL can be started with:

afl-fuzz -i /opt/argon2/input -o /opt/argon2/output-001 -M argon2-001 /opt/argon2/argon2-afl/argon2

Something like this should start:

                     american fuzzy lop 1.77b (argon2-001)

┌─ process timing ─────────────────────────────────────┬─ overall results ─────┐
│        run time : 0 days, 14 hrs, 36 min, 26 sec     │  cycles done : 2      │
│   last new path : 0 days, 0 hrs, 2 min, 27 sec       │  total paths : 1756   │
│ last uniq crash : 0 days, 6 hrs, 4 min, 4 sec        │ uniq crashes : 24     │
│  last uniq hang : 0 days, 12 hrs, 22 min, 16 sec     │   uniq hangs : 500+   │
├─ cycle progress ────────────────────┬─ map coverage ─┴───────────────────────┤
│  now processing : 1598 (91.00%)     │    map density : 2757 (4.21%)          │
│ paths timed out : 2 (0.11%)         │ count coverage : 2.14 bits/tuple       │
├─ stage progress ────────────────────┼─ findings in depth ────────────────────┤
│  now trying : havoc                 │ favored paths : 227 (12.93%)           │
│ stage execs : 74.1k/89.6k (82.70%)  │  new edges on : 1044 (59.45%)          │
│ total execs : 10.1M                 │ total crashes : 1967 (24 unique)       │
│  exec speed : 218.2/sec             │   total hangs : 341k (500+ unique)     │
├─ fuzzing strategy yields ───────────┴───────────────┬─ path geometry ────────┤
│   bit flips : 120/115k, 46/114k, 46/114k            │    levels : 13         │
│  byte flips : 8/14.4k, 11/14.0k, 4/13.2k            │   pending : 1356       │
│ arithmetics : 382/804k, 56/368k, 15/61.3k           │  pend fav : 49         │
│  known ints : 32/65.0k, 67/299k, 157/535k           │ own finds : 1638       │
│  dictionary : 0/0, 0/0, 87/495k                     │  imported : 116        │
│       havoc : 585/6.91M, 0/0                        │  variable : 1637       │
│        trim : 2.41%/3726, 0.00%                     ├────────────────────────┘
└─────────────────────────────────────────────────────┘             [cpu:204%]

I highly recommend you to set up your own AFL fuzzing instance (like a continuous testing environment). I'm not going to fuzz this project any further for now.

Now let's talk about the results. Turns out that argon2 segfaults on -m 94 or -m 95, but seem to wrap around (integer overflow?) when larger numbers are used (tested on 32bit and ARM):

$ ./argon2-asan/argon2 -m 93
Argon2i with
        t_cost = 3
        m_cost = 2097152
        password = password
        salt = 00000000000000000000000000000000
0.000 seconds (0.368 mebicycles)
4d8704087162b2bf2f00000000700508a247050803000000344cb2bf444cb2bf
$argon2i$m=2097152,t=3,p=4$AAAAAAAAAAAAAAAAAAAAAA$TYcECHFisr8vAAAAAHAFCKJHBQgDAAAANEyyv0RMsr8

$ ./argon2-asan/argon2 -m 94
Argon2i with
        t_cost = 3
        m_cost = 4194304
        password = password
        salt = 00000000000000000000000000000000
Segmentation fault

$ ./argon2-asan/argon2 -m 95
Argon2i with
        t_cost = 3
        m_cost = 8388608
        password = password
        salt = 00000000000000000000000000000000
Segmentation fault

$ ./argon2-asan/argon2 -m 96
Argon2i with
        t_cost = 3
        m_cost = 1
        password = password
        salt = 00000000000000000000000000000000
0.000 seconds (0.304 mebicycles)
4d8704087102e9bf2f00000000700508a247050803000000d4f2e8bfe4f2e8bf
$argon2i$m=1,t=3,p=4$AAAAAAAAAAAAAAAAAAAAAA$TYcECHEC6b8vAAAAAHAFCKJHBQgDAAAA1PLov+Ty6L8

Should be easy to reproduce. Here's a backtrace:

$ gdb --args ./argon2-asan/argon2 -m 95
GNU gdb (Ubuntu 7.7.1-0ubuntu5~14.04.2) 7.7.1
Copyright (C) 2014 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i686-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./argon2-asan/argon2...done.
(gdb) run
Starting program: /opt/argon2/argon2-asan/argon2 -m 95
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/i386-linux-gnu/libthread_db.so.1".
Argon2i with
        t_cost = 3
        m_cost = 8388608
        password = password
        salt = 00000000000000000000000000000000

Program received signal SIGSEGV, Segmentation fault.
blake2b_long (out=0x88058018 <error: Cannot access memory at address 0x88058018>, in=in@entry=0xbfffecf4, outlen=outlen@entry=1024, inlen=72) at src/blake2/blake2b-ref.c:320
320             memcpy( out, out_buffer, BLAKE2B_OUTBYTES / 2 );
(gdb) bt
#0  blake2b_long (out=0x88058018 <error: Cannot access memory at address 0x88058018>, in=in@entry=0xbfffecf4, outlen=outlen@entry=1024, inlen=72) at src/blake2/blake2b-ref.c:320
#1  0x08049b91 in fill_first_blocks (
    blockhash=blockhash@entry=0xbfffecf4 "\253\230\367\374W\024\315\204\326X\344\070\331I\267\311\200)\300\337\330\027\b\215\062\240\347\037\236n\377\213\027\333\213\330\n\034,\203m\227\206\224F\017\020*\334\016\071LW\301\206a\bV\376#A~\"<", instance=instance@entry=0xbfffed6c) at src/core.c:500
#2  0x08049f4b in initialize (instance=instance@entry=0xbfffed6c, context=context@entry=0xbfffee2c) at src/core.c:620
#3  0x0804a187 in argon2_core (context=context@entry=0xbfffee2c, type=type@entry=Argon2_i) at src/core.c:660
#4  0x08049227 in argon2i (context=context@entry=0xbfffee2c) at src/argon2.c:159
#5  0x0805412f in run (out=out@entry=0xbffff02c "M\207\004\bo\362\377\277/", pwd=pwd@entry=0x0, t_cost=t_cost@entry=3, m_cost=m_cost@entry=8388608, lanes=lanes@entry=4, 
    threads=threads@entry=4, type=type@entry=0x8054df6 "i", print=print@entry=false) at src/main.c:225
#6  0x08048baa in main (argc=3, argv=0xbffff104) at src/main.c:405

ASAN (address sanitizer) doesn't seem to catch the bug.

I know that an attacker controlling the m_cost of argon2 is probably a bad idea anyway and shouldn't happen, however, I do expect such a crypto tool to be rock solid.

Moreover I got various crashes that are not reproducible with vanilla argon2, but are probably poping up because of the memory restrictions that AFL enforces (for performance reasons, 25MB here, you can change that with -m to afl-fuzz). While I can't confirm this is an issue it might be worth checking how argon2 performs in memory limited environments.

[khovratovich]

What is the RAM capacity of your machine? We observe that Argon2 behaves in a strange way when the requested memory exceeds the physical amount of RAM, but have not reproduced the bug on our machines yet.

[floyd-fuh]

512MB on x86
2048MB on ARM

On OSX with 16GB RAM and x86_64 it works fine:

./argon2-plain/argon2 -m 94 -t 1
Argon2i with
    t_cost = 1
    m_cost = 4194304
    password = password
    salt = 00000000000000000000000000000000
16.357 seconds (20866.697 mebicycles)
4d8ca25fe2312b8dbb61c19ecf6f2a92e9c908ac7c2ecc2249bdebfee41f305f
$argon2i$m=4194304,t=1,p=4$AAAAAAAAAAAAAAAAAAAAAA$TYyiX+IxK427YcGez28qkunJCKx8LswiSb3r/uQfMF8

[daniel-dinu]

There is a problem with the memory allocation on 32-bit platforms:
*memory = ( block * )malloc( sizeof( block )*m_cost );
The sizeof( block )*m_cost creates a value overflow.

[daniel-dinu]

I added a check for integer overflow in commit b7e5cc7.

[khovratovich]

Please check if it works now.

[veorq]

@floyd-fuh could you test the latest version?

[floyd-fuh]

Let's say it works, but it's not really obvious what happens for each invocation...

(Btw. as a side note, look at the first invocation I did, that's why having a clean interface from the beginning is so important and you might want to reconsider the decision for using positional arguments for pwd and salt, maybe you just want to rather have arguments -p and -s that are mandatory, but this is off-topic for this bug)

/opt/argon2$ ./argon2-plain/argon2 -m 95
$argon2i$m=4096,t=3,p=4$OTUAAAAAAAAAAAAAAAAAAA$vaNpvIdMXmQyNwmQJNJTaXQzjqel84NkZ50162fuHts
0.065 seconds (168.887 mebicycles)

/opt/argon2$ ./argon2-plain/argon2
Usage:  ./argon2-plain/argon2 pwd salt [-y version] [-t t_cost] [-m m_cost] [-l #lanes] [-p #threads]
Options:
    pwd     The password to hash (required)
    salt        The salt to use, at most 16 characters (required)
    -y version  Argon2 version, either d or i (default)
    -t t_cost   Number of rounds to t_cost between 1 and 2^24, default 3
    -m m_cost   Memory usage of 2^t_cost kibibytes, default 12]
    -p N        Parallelism, default 4

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 1000
$argon2i$m=4096,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$HXAuomtsL0QJJSNcuyfroRSi5WcVpzSGqL7lcnMInlk
0.085 seconds (221.899 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 94
$argon2i$m=64,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$WUw36byNPpT9bQ8/UQGpOhyzicE4Hss28epL/NO7/xs
0.003 seconds (7.723 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 95
$argon2i$m=128,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$XKPy7mLAzmc4Y0+bPf5QwTRgVH6TCG7Wv6bqxZvr//k
0.004 seconds (12.011 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 96
$argon2i$m=256,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$2191xjNO7IZ9fs4PEWgaeLz0BCweXFoXg4GdUb148pU
0.005 seconds (12.505 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 97
$argon2i$m=512,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$v17VWFyM5VQGuWiJZzUJDhibp4eyQb2gtw3OW/PJjpg
0.005 seconds (18.696 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 98
$argon2i$m=1024,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$L39T17z5MesimYAigCl5ECcj/sQXqhi7c7ML8Z/4Uos
0.014 seconds (35.533 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 93
$argon2i$m=32,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$AyUGYtVepLYb8IgDwCqpYT7XWb0exlp6CwExgbKkXe0
0.003 seconds (8.458 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 92
$argon2i$m=16,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$boQfdvc9g4ULCGxTijuVawU7eVM8Fpv8n2O3kOiKLaE
0.003 seconds (9.343 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 91
$argon2i$m=8,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$CVt16pdG7Jg3ToyfIw2RIYCB5eqvLQI07HkLN8QkAz0
0.002 seconds (5.960 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 90
$argon2i$m=4,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$mYYECH6n+78vAAAAAHAFCEJCBQgFAAAAxJ37v9yd+78
0.000 seconds (0.161 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 89
$argon2i$m=2,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$mYYECH63vb8vAAAAAHAFCEJCBQgFAAAAVKe9v2ynvb8
0.000 seconds (0.133 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 88
$argon2i$m=1,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$mYYECH4n0b8vAAAAAHAFCEJCBQgFAAAAlA7Rv6wO0b8
0.000 seconds (0.135 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 87
^C

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 0
$argon2i$m=1,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$mYYECH+3zr8vAAAAAHAFCEJCBQgFAAAAdLLOv4yyzr8
0.000 seconds (0.163 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m -1
$argon2i$m=8192,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$Q+RKUaPUm9PQLx4Cd2Fdrq0DChAKN2/kZVaaq+gwAgg
0.105 seconds (1780.691 mebicycles)

/opt/argon2$ ./argon2-plain/argon2 abcd saltsaltsalt -m 2
$argon2i$m=4,t=3,p=4$c2FsdHNhbHRzYWx0AAAAAA$mYYECH8H0r8vAAAAAHAFCEJCBQgFAAAANOzRv0zs0b8
0.000 seconds (0.138 mebicycles)

I don't have a clue what's happening with -m 87, but it just takes very long.

[veorq]

Thanks, there's definitely something going wrong here.

Problem is at https://github.com/P-H-C/phc-winner-argon2/blob/master/src/main.c#L348, and due to 87 % 22 = 21 :-)

[khovratovich]

On the 32-bit machine the maximum requested memory is 2 GiB, which is delivered by -m 21 and -m 87 (and all other values equal to 21 mod 22).

I suppose that 2 GiB is still too much for your machine.

[floyd-fuh]

then maybe argon2 should just print an error message and gracefully exit?

[khovratovich]

It should gracefully exit in case of such errors but I can not reproduce where it fails at your side.

I will try to add more error message printing anyway.

[floyd-fuh]

It's just a Virtualbox 32bit machine with an installed Xubuntu image you can assign as much memory as you like for every start of the machine. Additionally you could install AFL as mentioned above on the same box, which can restrict memory (-m switch). Of course you can also use other Linux features to restrict memory of the argon2 process.

Additionally, I guess at one point you should seriously build continuous testing with AFL or another fuzzer of your choice. It will catch bugs early in the development process, like the segmentation fault we were talking about here in this issue report earlier on. It will increase security and usability and maybe most important for you: credibility in the security community for testing your code properly. In your case it is even incredibly simple, I gave you a step by step procedure above. In other words: If a memory corruption bug like this shows up in 10 years when people might be using argon2 you will regret that you didn't use a server CPU idling around somewhere or didn't take the time to setup a Virtualbox. In fact I didn't run the fuzzer again on your committed fixes. Of course you might have other things on the todo list at the moment.

Let me know if you already tried those approaches to reproduce the error and I'll be happy to help figuring it out further

[khovratovich]

You're right, we'll be working n that.

[sneves]

The most recent commit should be more resilient to such things.

[veorq]

Closing this one, thanks a lot @floyd-fuh for the testing, please let us know any other issue :)