Strange behavior with -pg and optimization when generating hashes

Question

I decided to make a program to find a sha3-512 hash with a certain number of zeroes at the start (like hashcash). It was working fine in my initial tests, so i decided to profile it with gprof to see if I could make it faster. After I had compiled with -pg and run it, I though i should go buy a lotto ticket. On the very first nonce I got a hash with 8 zeroes. However, I ran it again and I again got a number with 8 zeroes at the start. In fact, there were many discernible patterns in the hashes. After a few tests, I found that this only happened if I compiled with -pg and one of -O1, -O2, and -O3.

Here is the program

#include <tomcrypt.h>
#include <string.h>
#include <time.h>
#include <stdbool.h>
#include <stdio.h>

unsigned char* randstring(size_t length) {
    srand(time(NULL));
    unsigned char* randomString = NULL;

    if (length) {
        randomString = malloc(sizeof(char) * (length));

        if (randomString) {
            for (int n = 0; n < length; n++) {
                int key = rand() % 255;
                randomString[n] = (unsigned char)key;
            }
        }
    }

    return randomString;
}

void find_nonce(int zeroes, int* nonce_ptr, unsigned char* returner) {
    unsigned char string[40];
    unsigned char* rand_string = randstring(30);

    memcpy(string, rand_string, 30);
    free(rand_string);
    //string is longer than rand_string because i need romm to put the nonce in

    int nonce = 0;

    int idx;

    if (register_hash(&sha3_512_desc) == -1) {
        printf("Error registering SHA3-512.\n");
        exit(1);
    }
    idx = find_hash("sha3-512");
    if (idx == -1) {
        printf("Invalid hash name!\n");
        exit(1);
    }

    int res_bool = false;
    unsigned char res[64];
    unsigned long res_size;
    char nonce_str[11];
    int nonce_len = 0;

    while (!res_bool) {
        //Put the nonce into a string
        sprintf(nonce_str, "%d", nonce);

        //Put the nonce string into the string as an unsigned char (hash_memory takes an unsigned char)
        for (int i = 0, j = 11;; ++i, ++j) {
            if (nonce_str[i] == '\0') {
                break;
            }
            string[j] = (unsigned char)nonce_str[i];
            nonce_len++;

        }

        //Hash it
        hash_memory(idx, string, 30+nonce_len, res, &res_size);

        nonce_len = 0;

        //Check if the string has a sufficient number of zeroes at the start
        res_bool = true;
        for (int i = 0; i < zeroes; i++) {
            if ((int)res[i] != 0) {
                res_bool = false;
                break;
            }
        }
        nonce++;

    }
    *nonce_ptr = nonce;

    for (int i = 0; i < 64; i++) {
        returner[i] = res[i];
    }
}

int main(int argc, char** argv) {
    //Getting command-line arguments
    int zeroes = atoi(argv[argc - 1]);
    
    int nonce;
    unsigned char hash[64];

    //Timing the execution
    clock_t start, end;
    double cpu_time_used;

    start = clock();

    find_nonce(zeroes, &nonce, hash);

    end = clock();
    cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;

    //Printing the output to the screen
    printf("Hash was ");
    for (int i = 0; i < 64; i++) {
        printf("%d ", (int)hash[i]);
    }
    printf("\nNonce to get the hash was %d\nIt took %f seconds to calculate\n", nonce, cpu_time_used);

    return 0;
}

And here is an example output from five tests:

Hash was 0 0 0 0 0 0 0 0 6 203 85 177 228 127 0 0 192 128 164 212 252 127 0 0 129 219 85 177 228 127 0 0 0 235 105 177 228 127 0 0 144 128 164 212 252 127 0 0 2 0 0 0 0 0 0 0 48 130 164 212 252 127 0 0 
Nonce to get the hash was 1
It took 0.000000 seconds to calculate

Hash was 0 0 0 0 0 0 0 0 6 203 214 123 135 127 0 0 64 216 207 126 253 127 0 0 129 219 214 123 135 127 0 0 0 235 234 123 135 127 0 0 16 216 207 126 253 127 0 0 2 0 0 0 0 0 0 0 176 217 207 126 253 127 0 0 
Nonce to get the hash was 1
It took 0.000000 seconds to calculate

Hash was 0 0 0 0 0 0 0 0 6 123 219 55 192 127 0 0 144 108 17 232 252 127 0 0 129 139 219 55 192 127 0 0 0 155 239 55 192 127 0 0 96 108 17 232 252 127 0 0 2 0 0 0 0 0 0 0 0 110 17 232 252 127 0 0 
Nonce to get the hash was 1
It took 0.000000 seconds to calculate

Hash was 0 0 0 0 0 0 0 0 6 107 181 157 222 127 0 0 64 183 143 12 253 127 0 0 129 123 181 157 222 127 0 0 0 139 201 157 222 127 0 0 16 183 143 12 253 127 0 0 2 0 0 0 0 0 0 0 176 184 143 12 253 127 0 0 
Nonce to get the hash was 1
It took 0.000000 seconds to calculate

Hash was 0 0 0 0 0 0 0 0 6 139 121 81 110 127 0 0 32 171 61 179 254 127 0 0 129 155 121 81 110 127 0 0 0 171 141 81 110 127 0 0 240 170 61 179 254 127 0 0 2 0 0 0 0 0 0 0 144 172 61 179 254 127 0 0 
Nonce to get the hash was 1
It took 0.000000 seconds to calculate

Have you tried stepping through the code with debugger? Running it under *valgrind*? At a glance it looks like you may calculate hash from partially uninitialized `string`, unless I missed something. — hyde, Aug 09 '22 at 18:19
I tried running it through with valgrind but it gives an even stranger output: a hash with all zeroes. As for the string, I specify the amount of bytes to read from the string when calling hash_memory. — drake14w, Aug 09 '22 at 18:27
Where do you initialize the last bytes of `string`? This is one of the rare cases where `strncpy` does excatly what your loop tries to do, btw. — hyde, Aug 09 '22 at 18:29
I set hash_memory to only read the initialized bytes from string. The last bytes are initialized when the nonce gets very large e.g. 4,327,298,965. — drake14w, Aug 09 '22 at 18:39
Ah, yeah, it's now fixed, I was commenting on the original version without `nonce_len` variable. — hyde, Aug 10 '22 at 06:32

score 1 · Accepted Answer · answered Aug 09 '22 at 19:20

1

res_size is not initialized. It contains garbage, and the garbage is different depending on the compiler flags.

hash_memory, on the other hand, expects it to have the size of the output buffer. The first thing it does is to check that there is enough space provided, and if not it bails out.

So what you see are not hashes, but initial state of your buffer.

Always test the return values!

answered Aug 09 '22 at 19:20

user58697

7,808
1
14
28

Thank you, this was the problem. – drake14w Aug 09 '22 at 19:36

Strange behavior with -pg and optimization when generating hashes

1 Answers1