Why do i get more 256 false positive in PKZIP Decryption key verification?

Question

I have been trying to brute force Key2 of ZipCrypto with first byte of CRC and last byte of encryption header to see how long would it take but i got more than 2000 valid keys. From the APPNOTE, Key2 is the used to decrypt a byte and Key2 is a result of CRC32 meaning it is a 32 bit value which should be found within the range 2147483648 to 2147483648*2.

The password for this test stream is

1234

and the CRC is

77D7DCDE

Then the stream:

50 4B 03 04 14 00 01 00 08 00 68 99 6D 58 DE DC D7 77 CB 82 07 00 0F B1 0A 00 09 00 00 00 6B 65 79 73 30 2E 74 78 74 50 3F 83 D5 C7 D4 69 6E 9B B9 E9 F2 DD 16 D5 EA 5B 41 F9 BC 59 6E 34 E8 2F 2B 49 4E DD 90 3E D8 65 5E 21 42 E6 8C 8C AD 8E

Here is the code sample:

#ifdef LINUX

#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>

typedef pthread_t thread;
typedef pthread_mutex_t mutex;

static inline void mutex_init(mutex *m)
{
    int res = pthread_mutex_init(m, NULL);
    assert(res == 0);
}

static inline void mutex_lock(mutex *m)
{
    int res = pthread_mutex_lock(m);
    assert(res == 0);
}

static inline void mutex_unlock(mutex *m)
{
    int res = pthread_mutex_unlock(m);
    assert(res == 0);
}

static thread spawn_thread(void *(f)(void *), void *arg)
{
    thread t;
    int res = pthread_create(&t, NULL, f, (void *)arg);
    if (res != 0)
        return (thread)NULL;
    return t;
}

static void join_thread(thread t)
{
    pthread_join(t, NULL);
}

static size_t num_threads(void)
{
    return (size_t)sysconf(_SC_NPROCESSORS_ONLN);
}


static uint64_t get_time(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1000 + ts.tv_nsec / 1000000;
}

#endif


unsigned char decrypt_byte(size_t Key2) {
    uint32_t dkey = Key2;
    unsigned short temp = dkey | 2;
    return (temp * (temp ^ 1)) >> 8;
}


static bool bytecheck(const unsigned char dat)
{
    unsigned char targ = 0x77;//first byte of my Checksum
    
    if(dat == targ)
       {
            return true;
        }
    return false;
}


struct info
{
    unsigned char buffer;
    size_t start;
    size_t end;
};

// Stop when a thread finds a solution.
static volatile bool stop = false;
static void *worker(void *arg);

static thread spawn_worker( size_t start, size_t end, unsigned char buffer)
{
    struct info *info = (struct info *)malloc(sizeof(struct info));
    assert(info != NULL);
    info->start = start;
    info->end = end;
    info->buffer = buffer;
    thread t = spawn_thread(worker, info);
    if (t == (thread)NULL)
    {
        fprintf(stderr, "error: failed to spawn thread");
        exit(EXIT_FAILURE);
    }
    return t;
}
static void *worker(void *arg)
{
    struct info *info = (struct info *)arg;
    size_t start = info->start;
    size_t end = info->end;
    unsigned char buf = info->buffer;
    free(info);
    for(size_t i =start; i < end+1; i++)
    {
        if (stop)
            return NULL;
        unsigned char res = decrypt_byte(i);
        unsigned char C = buf ^ res;

        if (bytecheck(C))
        {
            printf("%zu\n",i);
            stop = true;
            return NULL;
        }
    }

}

//gcc ben.c -pg --std=gnu99 -lz -lm -lpthread -o zipcr

int main()
{

    size_t NUM_WORKERS = num_threads();
    printf("threads = %lu\n", NUM_WORKERS);
    uint64_t t0 = get_time();
    size_t tap = 2147483648;
    size_t port = tap / NUM_WORKERS;
    thread ts[NUM_WORKERS];
    for (size_t i = 0; i < NUM_WORKERS; i++)
        {
            size_t start = tap+ (i*port);
            size_t end = start+port;
            unsigned char buffer = 0xF2;
            ts[i] = spawn_worker(start, end,buffer);
        }
        for (size_t i = 0; i < NUM_WORKERS; i++)
            join_thread(ts[i]);
    uint64_t t1 = get_time();
    printf("\ntime = %lums\n", t1 - t0);

return 0;
}

Why am i getting so many false positive, what is wrong with my code?

Answer 1

All of that reduces to this:

#include <stdio.h>

int main(void) {
    size_t tap = 2147483648;
    for (size_t i = tap; i < 2 * tap + 1; i++) {
        unsigned short temp = i | 2;
        unsigned char ch = 0xf2 ^ ((temp * (temp ^ 1)) >> 8);
        if (ch == 0x77)
            printf("%zu\n", i);
    }
    return 0;
}

except, that I removed the "stop", so that all results are printed. (By the way, this runs in about two seconds on my machine, so I don't get what the point of all the threading is.)

This prints 8388608 results, which is 1/256 of the number of iterations (minus one). Exactly what you'd expect when checking one byte randomly generated. There is nothing surprising here. What were you expecting?

However running it on 2³¹ cases (plus one for some reason) makes no sense, since the input to the query is only 16 bits (a short)! Or really only 15 bits after the | 2. You only need 32768 iterations to explore the entire domain of your function.