Hide behind huge numbers, making fighting against very expensive

Birthday problem or paradox is the probability that, from a given set of people, two of them will have the same birthday. It is a paradox because the result defies common sense. For a group of 23 people, the chance that two of them share the same birthday is greater than 50%, and for a group of 57 people, it is higher than 99%.

The best known use of Birthday Problem paradox is probably the Cryptographic Attack known as the Birthday Attack. This attack exploits the math behind the Birthday Paradox, by looking for collisions in a small set, having a much higher collision chance than expected.

Recently I came across a different use of the same paradox, in what else than the infamous Conficker. Here, the use of this statistical paradox is different, with the purpose of making the fight against this worm much harder.

Here is the problem explained: each day, they have a pool of 50,000 (pseudo)randomly generated URLs, out of each any infected computer randomly chooses 500. The total number of possible draws is huge. It actually has 1,215 digits in decimal representation and people will find hard even to imagine it. Just for the fun of it, I annexed the file to the end of my post. However, as you will see, in practice things work on a much smaller scale.

Registering all of them is an incredibly challenging task, and here lies the power of the aforementioned statistical problem. The problem here is to find the probability that a random group of 500 URLs contains at least one out of a smaller set (I will refer to such cases from here on as hits). And the result is amazing: if one registers 50 URLs, the chance to hit is 39.514%, and if one registers 500 URLs the chance to hit becomes 99.359%. That is, with only 1% of the pool registered, one can achieve more than 99% success rate in spreading new malware content using Conficker.

The graph of hit chance is here

On the horizontal axis we have the number of registered URLs and on the vertical axis we have the chance that any random draw will hit at least one of them, or in other words, the chance that a computer infected with Conficker will access one of these URLs.

This shows the importance of blocking as many of the 50,000 URLs as possible. A single missed URL that happens to be registered for malicious purpose can get 1% chance to spread malware to Conficker infected machines.

Randomly blocking some of the URLs have limited benefits, since the pool size is fairly big and the number of URLs potentially used by the malware is relatively small (at least two orders of magnitude).

Even if the above statement is true, there are some particularities that may help overcome these facts. The domains have to be registered through a limited number of Registrars, based on their TLD. By working with the registrars directly, bulkily blocking large numbers of domains becomes less of a problem than Conficker’s authors had foreseen, and with all the attention this thing is getting, people are willing to put in a lot of work to see this threat over.

The “good guys” also may use this paradox to their own advantage. It may give means in estimating the real size of the “infection” in the world. By registering a limited numbers of URLs, one can monitor the incoming requests, and knowing the chance a URL is picked, one can extrapolate to the number of infected machines.

Appendix 1 - Mathematical reasoning behind the numbers I’ve presented here.

Let’s denote by C(n,k) the number of combinations of size k chosen from a set of n elements (S). Our problem is to determine the probability that a randomly chosen set hit at least one element from a smaller subset of S. Let m be the number of elements in that smaller set. M is the subset of S, having Card(M) = m. The total number of possible k sized sets out of S is C(n,k).

In order to see how many of them contain at least an element from M we check first its complement. That is, the number of k-sets that do not contain an element from M. It is obvious that to have such sets, m has to be smaller than or equal to n– k. In other words if m is greater than n– k, there is no possible choice of k-sets that do not contain elements from M. If m is smaller than n– k and we subtract M from S (S\M) we get a subset of S, denoted by S’ that has n– m elements. It is clear that all k-sets from S that do not contain elements from M are also k-sets for S’, and all k-sets from S’ are also k-sets for S, so the sets are equivalent. Thus the number of k-sets from S that do not contain elements from M is equal to the number of k-sets from S’ which is equal to C(n-m,k).

As a direct result, the number of k-sets from S containing at least an element from M is C(n,k)–C(n-m,k). In order to compute the probability we divide this number by the total number of sets. We get P(m) = 1 – C(n–m,k)/C(n,k). If we break this down we get to

As we see, the second element is a product of sub-unitary numbers, which decreases towards 0 as we increase the number of elements (m). As a matter of fact, each element in the product is smaller than the first element (n–k)/n (trivial to prove under the assumption 1=j=m=n-k) resulting in the following approximation,

that is closing to 0 faster than an exponential. This means that our probability can be approximated with the following formula
Another debate may be started around the fact Conficker doesn't check for duplicates when picking up the 500 URLs. To take this into account, we have to estimate the average number of duplicates in a randomly picked 500 set out of the bigger 50,000 possible choices. A collision counting formula may be found at Collision counting formula. Applying the formula on our case, gives an estimate of 2.4867 duplicates on any random draw. To take this into account, we have to adjust previous calculations with 497 instead of 500, but this doesn't induce a notable difference in the results.

Another approach for the same arguments is to take into account the number of combinations with repetitions, rather than the number of combinations. This changes the above formulas to C(n+k–1,k) used instead of C(n,k); Combinations with repetitions. Having the following substitution n'=n+k–1 we get to the same formulas, but n' used in place of n. The differences in the numbers above are insignificant, and this is true for similar cases: n much bigger in comparison with k.

Appendix 2 - Here is a table showing the probabilities to get a hit for up to 100 URLs. The values are computed with the exact formula, not using the approximation, but in most cases, especially with large numbers, the estimation gives a pretty good idea.

 #Chosen URLs Chance to hit 1 1.00% 26 23.00% 51 40.12% 76 53.44% 2 1.99% 27 23.77% 52 40.72% 77 53.91% 3 2.97% 28 24.53% 53 41.31% 78 54.37% 4 3.94% 29 25.29% 54 41.90% 79 54.82% 5 4.90% 30 26.04% 55 42.48% 80 55.28% 6 5.85% 31 26.78% 56 43.06% 81 55.72% 7 6.79% 32 27.51% 57 43.63% 82 56.17% 8 7.73% 33 28.23% 58 44.19% 83 56.61% 9 8.65% 34 28.95% 59 44.75% 84 57.04% 10 9.56% 35 29.66% 60 45.30% 85 57.47% 11 10.47% 36 30.37% 61 45.85% 86 57.90% 12 11.36% 37 31.06% 62 46.39% 87 58.32% 13 12.25% 38 31.75% 63 46.93% 88 58.74% 14 13.13% 39 32.44% 64 47.46% 89 59.15% 15 14.00% 40 33.11% 65 47.99% 90 59.56% 16 14.86% 41 33.78% 66 48.51% 91 59.96% 17 15.71% 42 34.45% 67 49.02% 92 60.37% 18 16.55% 43 35.10% 68 49.53% 93 60.76% 19 17.39% 44 35.75% 69 50.04% 94 61.16% 20 18.21% 45 36.39% 70 50.54% 95 61.55% 21 19.03% 46 37.03% 71 51.04% 96 61.93% 22 19.84% 47 37.66% 72 51.53% 97 62.31% 23 20.64% 48 38.29% 73 52.01% 98 62.69% 24 21.44% 49 38.90% 74 52.49% 99 63.06% 25 22.22% 50 39.51% 75 52.97% 100 63.43%

Appendix 3 - Number of 500 sized groups out of a pool of 50,000

204,834,213,151,168,214,461,654,141,379,130,974,442,702,258,579,159,760,519,079,012,459,387,176,802,
787,506,861,786,508,179,331,441,121,439,711,042,255,209,315,604,421,328,946,422,708,973,054,967,511,
463,454,539,076,329,708,371,835,003,639,384,418,663,768,257,135,542,695,566,118,398,524,969,107,678,
840,406,278,808,768,917,987,669,580,920,601,539,854,184,448,084,968,926,599,909,629,237,703,403,693,
367,099,024,184,779,484,619,888,559,300,860,309,406,196,851,763,668,717,714,332,015,184,499,781,085,
279,838,674,767,933,215,516,613,767,486,445,885,103,234,075,164,696,519,772,065,511,437,536,446,581,
389,706,964,561,561,630,111,372,422,588,407,655,472,487,156,160,979,442,796,737,751,214,470,874,983,
713,716,166,016,097,542,640,445,995,015,124,162,692,362,933,579,204,387,223,639,162,341,095,056,558,
194,384,376,095,685,557,088,871,687,075,022,514,166,924,615,039,210,753,372,304,959,038,121,674,413,
419,287,592,963,128,974,892,289,843,707,783,982,076,564,230,128,288,660,514,687,421,957,578,018,027,
099,724,820,158,186,441,086,224,228,396,845,701,885,741,875,315,754,256,285,000,948,322,222,787,948,
002,673,558,400,910,506,477,079,314,973,748,069,999,035,196,658,450,861,075,755,112,300,624,257,908,
109,473,126,745,582,249,777,744,799,202,563,038,549,934,781,898,593,761,740,878,642,558,088,366,365,
761,869,077,984,254,942,611,411,570,900,277,727,137,416,203,980,580,420,283,292,933,330,096,057,462,
249,072,976,977,887,327,330,947,186,730,927,061,671,007,370,705,441,238,632,455,277,914,656,553,937,
760,943,654,927,229,770,344,284,531,443,702,460,460,473,920,711,298,545,759,340,018,169,550,420,491,
173,318,117,302,400

--Dan Nicolescu