123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164 |
- /*
- * ZMap Copyright 2013 Regents of the University of Michigan
- *
- * Licensed under the Apache License, Version 2.0 (the "License"); you may not
- * use this file except in compliance with the License. You may obtain a copy
- * of the License at http://www.apache.org/licenses/LICENSE-2.0
- */
- /*
- * cyclic provides an inexpensive approach to iterating over the IPv4 address
- * space in a random(-ish) manner such that we connect to every host once in
- * a scan execution without having to keep track of the IPs that have been
- * scanned or need to be scanned and such that each scan has a different
- * ordering. We accomplish this by utilizing a cyclic multiplicative group
- * of integers modulo a prime and generating a new primitive root (generator)
- * for each scan.
- *
- * We know that 3 is a generator of (Z mod 2^32 + 15 - {0}, *)
- * and that we have coverage over the entire address space because 2**32 + 15
- * is prime and ||(Z mod PRIME - {0}, *)|| == PRIME - 1. Therefore, we
- * just need to find a new generator (primitive root) of the cyclic group for
- * each scan that we perform.
- *
- * Because generators map to generators over an isomorphism, we can efficiently
- * find random primitive roots of our mult. group by finding random generators
- * of the group (Zp-1, +) which is isomorphic to (Zp*, *). Specifically the
- * generators of (Zp-1, +) are { s | (s, p-1) == 1 } which implies that
- * the generators of (Zp*, *) are { d^s | (s, p-1) == 1 }. where d is a known
- * generator of the multiplicative group. We efficiently find
- * generators of the additive group by precalculating the psub1_f of
- * p - 1 and randomly checking random numbers against the psub1_f until
- * we find one that is coprime and map it into Zp*. Because
- * totient(totient(p)) ~= 10^9, this should take relatively few
- * iterations to find a new generator.
- */
- #include "cyclic.h"
- #include <stdlib.h>
- #include <stdio.h>
- #include <stdint.h>
- #include <time.h>
- #include <assert.h>
- #include <string.h>
- #include <math.h>
- #include <gmp.h>
- #include "../lib/includes.h"
- #include "../lib/logger.h"
- // We will pick the first cyclic group from this list that is
- // larger than the number of IPs in our whitelist. E.g. for an
- // entire Internet scan, this would be cyclic32
- // Note: this list should remain ordered by size (primes) ascending.
- static cyclic_group_t groups[] = {
- { // 2^8 + 1
- .prime = 257,
- .known_primroot = 3,
- .prime_factors = {2},
- .num_prime_factors = 1
- },
- { // 2^16 + 1
- .prime = 65537,
- .known_primroot = 3,
- .prime_factors = {2},
- .num_prime_factors = 1
- },
- { // 2^24 + 43
- .prime = 16777259,
- .known_primroot = 2,
- .prime_factors = {2, 23, 103, 3541},
- .num_prime_factors = 4
- },
- { // 2^28 + 3
- .prime = 268435459,
- .known_primroot = 2,
- .prime_factors = {2, 3, 19, 87211},
- .num_prime_factors = 4
- },
- { // 2^32 + 15
- .prime = 4294967311,
- .known_primroot = 3,
- .prime_factors = {2, 3, 5, 131, 364289},
- .num_prime_factors = 5
- }
- };
- #define COPRIME 1
- #define NOT_COPRIME 0
- // Check whether an integer is coprime with (p - 1)
- static int check_coprime(uint64_t check, const cyclic_group_t *group)
- {
- for (unsigned i=0; i < group->num_prime_factors; i++) {
- if (group->prime_factors[i] > check && !(group->prime_factors[i] % check)) {
- return NOT_COPRIME;
- } else if (group->prime_factors[i] < check && !(check % group->prime_factors[i])) {
- return NOT_COPRIME;
- } else if (group->prime_factors[i] == check) {
- return NOT_COPRIME;
- }
- }
- return COPRIME;
- }
- // Return a (random) number coprime with (p - 1) of the group,
- // which is a generator of the additive group mod (p - 1)
- static uint32_t find_primroot(const cyclic_group_t *group, aesrand_t *aes)
- {
- uint32_t candidate = (uint32_t) ((aesrand_getword(aes) & 0xFFFFFFFF) % group->prime);
- if (candidate == 0) {
- ++candidate;
- }
- while (check_coprime(candidate, group) != COPRIME) {
- ++candidate;
- //special case where we need to restart check from begin
- if(candidate >= group->prime) {
- candidate = 1;
- }
- }
- uint64_t retv = isomorphism(candidate, group);
- return retv;
- }
- const cyclic_group_t* get_group(uint64_t min_size)
- {
- for(unsigned i = 0; i < sizeof(groups); ++i) {
- if (groups[i].prime > min_size) {
- return &groups[i];
- }
- }
- // Should not reach, final group should always be larger than 2^32
- assert(0);
- }
- cycle_t make_cycle(const cyclic_group_t* group, aesrand_t *aes)
- {
- cycle_t cycle;
- cycle.group = group;
- cycle.generator = find_primroot(group, aes);
- cycle.offset = (uint32_t) (aesrand_getword(aes) & 0xFFFFFFFF);
- cycle.offset %= group->prime;
- return cycle;
- }
- uint64_t isomorphism(uint64_t additive_elt, const cyclic_group_t* mult_group)
- {
- assert(additive_elt < mult_group->prime);
- mpz_t base, power, prime, primroot;
- mpz_init_set_ui(base, mult_group->known_primroot);
- mpz_init_set_ui(power, additive_elt);
- mpz_init_set_ui(prime, mult_group->prime);
- mpz_init(primroot);
- mpz_powm(primroot, base, power, prime);
- uint64_t retv = (uint64_t) mpz_get_ui(primroot);
- log_trace("zmap", "Isomorphism: %llu", retv);
- mpz_clear(base);
- mpz_clear(power);
- mpz_clear(prime);
- mpz_clear(primroot);
- return retv;
- }
|