Skip to content

Commit c3c93c7

Browse files
v-byte-cpuv-byte-cpu
authored
feature: randomized IP iterator (#89)
1 parent 0906604 commit c3c93c7

File tree

6 files changed

+490
-15
lines changed

6 files changed

+490
-15
lines changed

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,7 @@ The goal of this project is to create the fastest network scanner with clean and
4242
* **SOCKS5 scan**: Detect live SOCKS5 proxies by scanning ip range or list of ip/port pairs from a file
4343
* **Docker scan**: Detect open Docker daemons listening on TCP ports and get information about the docker node
4444
* **Elasticsearch scan**: Detect open Elasticsearch nodes and pull out cluster information with all index names
45+
* **Randomized iteration** over IP addresses using finite cyclic multiplicative groups
4546
* **JSON output support**: sx is designed specifically for convenient automatic processing of results
4647

4748
## 📦 Install

‎command/root.go‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@ package command
22

33
import (
44
"context"
5+
"math/rand"
56
"os"
67
"sync"
78
"time"
@@ -15,6 +16,7 @@ import (
1516
)
1617

1718
func Main(version string) {
19+
rand.Seed(time.Now().Unix())
1820
if err := newRootCmd(version).Execute(); err != nil {
1921
os.Exit(1)
2022
}

‎pkg/scan/range.go‎

Lines changed: 281 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,281 @@
1+
package scan
2+
3+
import (
4+
"errors"
5+
"fmt"
6+
"math/big"
7+
"math/rand"
8+
"sort"
9+
)
10+
11+
var errRangeSize = errors.New("invalid range size")
12+
13+
// We will pick the first cyclic group from this list that is
14+
// larger than the range size
15+
var cyclicGroups = []struct {
16+
// Prime number for (Z/pZ)* multiplicative group
17+
P int64
18+
// Cyclic group generator
19+
G int64
20+
// Number coprime with P-1
21+
N int64
22+
}{
23+
{
24+
P: 3, // 2^1 + 1
25+
G: 2,
26+
N: 1,
27+
},
28+
{
29+
P: 5, // 2^2 + 1
30+
G: 2,
31+
N: 1,
32+
},
33+
{
34+
P: 11, // 2^3 + 3
35+
G: 2,
36+
N: 3,
37+
},
38+
{
39+
P: 17, // 2^4 + 1
40+
G: 3,
41+
N: 3,
42+
},
43+
{
44+
P: 37, // 2^5 + 5
45+
G: 2,
46+
N: 5,
47+
},
48+
{
49+
P: 67, // 2^6 + 3
50+
G: 2,
51+
N: 5,
52+
},
53+
{
54+
P: 131, // 2^7 + 3
55+
G: 2,
56+
N: 3,
57+
},
58+
{
59+
P: 257, // 2^8 + 1
60+
G: 3,
61+
N: 3,
62+
},
63+
{
64+
P: 523, // 2^9 + 11
65+
G: 2,
66+
N: 5,
67+
},
68+
{
69+
P: 1031, // 2^10 + 7
70+
G: 21,
71+
N: 3,
72+
},
73+
{
74+
P: 2053, // 2^11 + 5
75+
G: 2,
76+
N: 5,
77+
},
78+
{
79+
P: 4099, // 2^12 + 3
80+
G: 2,
81+
N: 5,
82+
},
83+
{
84+
P: 8219, // 2^13 + 27
85+
G: 2,
86+
N: 3,
87+
},
88+
{
89+
P: 16421, // 2^14 + 37
90+
G: 2,
91+
N: 3,
92+
},
93+
{
94+
P: 32771, // 2^15 + 3
95+
G: 2,
96+
N: 3,
97+
},
98+
{
99+
P: 65539, // 2^16 + 3
100+
G: 2,
101+
N: 5,
102+
},
103+
{
104+
P: 131101, // 2^17 + 29
105+
G: 17,
106+
N: 7,
107+
},
108+
{
109+
P: 262147, // 2^18 + 3
110+
G: 2,
111+
N: 5,
112+
},
113+
{
114+
P: 524309, // 2^19 + 21
115+
G: 2,
116+
N: 3,
117+
},
118+
{
119+
P: 1048589, // 2^20 + 13
120+
G: 2,
121+
N: 3,
122+
},
123+
{
124+
P: 2097211, // 2^21 + 59
125+
G: 2,
126+
N: 7,
127+
},
128+
{
129+
P: 4194371, // 2^22 + 67
130+
G: 2,
131+
N: 3,
132+
},
133+
{
134+
P: 8388619, // 2^23 + 11
135+
G: 2,
136+
N: 5,
137+
},
138+
{
139+
P: 16777259, // 2^24 + 43
140+
G: 2,
141+
N: 5,
142+
},
143+
{
144+
P: 33554467, // 2^25 + 35
145+
G: 2,
146+
N: 5,
147+
},
148+
{
149+
P: 67108933, // 2^26 + 69
150+
G: 2,
151+
N: 5,
152+
},
153+
{
154+
P: 134217773, // 2^27 + 45
155+
G: 2,
156+
N: 5,
157+
},
158+
{
159+
P: 268435459, // 2^28 + 3
160+
G: 2,
161+
N: 5,
162+
},
163+
{
164+
P: 536871019, // 2^29 + 107
165+
G: 2,
166+
N: 5,
167+
},
168+
{
169+
P: 1073741827, // 2^30 + 3
170+
G: 2,
171+
N: 5,
172+
},
173+
{
174+
P: 2147483659, // 2^31 + 11
175+
G: 2,
176+
N: 5,
177+
},
178+
{
179+
P: 4294967357, // 2^32 + 61
180+
G: 2,
181+
N: 5,
182+
},
183+
}
184+
185+
// newRangeIterator creates a pseudo-random iterator for
186+
// integer range [1..n]. Each integer is traversed exactly once.
187+
func newRangeIterator(n int64) (*rangeIterator, error) {
188+
// Here we apply cyclic groups
189+
// (Z/pZ)* is a multiplicative group if p is a prime number
190+
// also (Z/pZ)* is a cyclic group, to understand this fact I recommend to read
191+
// "When Is the Multiplicative Group Modulo n Cyclic?" paper by Aryeh Zax
192+
if n <= 0 {
193+
return nil, errRangeSize
194+
}
195+
196+
// find first cyclic group that is larger than n
197+
idx := sort.Search(len(cyclicGroups), func(i int) bool {
198+
return cyclicGroups[i].P > n
199+
})
200+
if idx == len(cyclicGroups) {
201+
return nil, errRangeSize
202+
}
203+
cyclic := cyclicGroups[idx]
204+
P, G, N := big.NewInt(cyclic.P), big.NewInt(cyclic.G), big.NewInt(cyclic.N)
205+
206+
// first of all, we apply group theory facts for cyclic groups:
207+
// 1. Let T be a finite cyclic group of order n. Let G be a generator. Let r be an
208+
// integer != 0, and relatively prime to n. Then (G ** r) is also a generator of T.
209+
// 2. Fermat's little theorem:
210+
// if p is a prime number then for any integer a: (a ** (p-1)) mod p = 1.
211+
// See Chapter 2, Exercise 17 on page 26 and Theorem 4.3 (Lagrange's theorem)
212+
// in the "Undergraduate Algebra" Third Edition by Serge Lang
213+
214+
// number of elements of (Z/pZ)* is equal to P-1
215+
// randM is a random integer
216+
randM := big.NewInt(rand.Int63())
217+
one := big.NewInt(1)
218+
randM.Add(randM, one)
219+
// if N is coprime with P-1 => (N ** randM) is coprime with P-1
220+
// by Fermat's little theorem: (G ** M) mod P = (G ** (M mod (P-1))) mod P for any integer M
221+
// prepare new group generator:
222+
// G - generator, (N ** randM) is coprime with group order => G = (G ** (N ** randM)) mod P is also a generator
223+
N.Exp(N, randM, big.NewInt(cyclic.P-1))
224+
G.Exp(G, N, P)
225+
226+
// select a random element from which to start the iteration: randI = (G ** randM) mod P
227+
randM.SetInt64(rand.Int63()).Add(randM, one)
228+
randI := big.NewInt(0).Exp(G, randM, P)
229+
230+
it := &rangeIterator{P: P, G: G,
231+
rangeLimit: big.NewInt(n),
232+
I: big.NewInt(0).Set(randI),
233+
startI: big.NewInt(0).Set(randI),
234+
}
235+
236+
// find a first number I <= n from which to start the iteration
237+
if !it.Next() && n > 1 {
238+
return nil, fmt.Errorf("invalid cyclic group: P = %+v G = %+v N = %+v startI = %+v",
239+
P, G, N, it.startI)
240+
}
241+
it.startI.Set(it.I)
242+
return it, nil
243+
}
244+
245+
type rangeIterator struct {
246+
// Prime number for (Z/pZ)* multiplicative group
247+
P *big.Int
248+
// Cyclic group generator
249+
G *big.Int
250+
// Current number
251+
I *big.Int
252+
// the number at which the iteration starts
253+
startI *big.Int
254+
255+
// right boundary of the range
256+
rangeLimit *big.Int
257+
stop bool
258+
}
259+
260+
func (it *rangeIterator) Next() bool {
261+
if it.stop {
262+
return false
263+
}
264+
for {
265+
// I = (I * G) mod P
266+
it.I.Mul(it.I, it.G)
267+
it.I.Mod(it.I, it.P)
268+
if it.I.Cmp(it.startI) == 0 {
269+
it.stop = true
270+
return false
271+
}
272+
// if i <= rangeLimit
273+
if it.I.Cmp(it.rangeLimit) < 1 {
274+
return true
275+
}
276+
}
277+
}
278+
279+
func (it *rangeIterator) Int() *big.Int {
280+
return it.I
281+
}

0 commit comments

Comments
 (0)