Canadian PRNG expert criticizes authorities for using ancient Excel algorithms to play for visas

The Family Reunification Program or Family sponsorship is one of the three main Canadian migrant assistance programs. It allows both newly arrived immigrants and long-established Canadians to reunite with their family members. In accordance with the immigration and refugee protection regulations (Immigration and Refugee Protection Regulations), families living abroad receive financial assistance, as well as migrant relatives living in Canada. Spouses, children, parents, grandchildren, adopted children, etc., can count on financial assistance.

The problem is that Canada cannot immediately grant citizenship to all relatives of all migrants. Previously, they were put in a queue, and consideration of the application had to wait for years. To speed up the process, the liberals offered to hold a lottery. So from 2017, a lottery of the American Green Card has been played in Canada. Of the approximately 100,000 applications, 10,000 are randomly selected. Thanks to the official response to the request under the Law of Access to Information, the Canadian publication The Globe an Mail has learned some technical details about how the lottery is conducted.

It turns out that the federal government selects winners using Microsoft Excel. Here is what the whole procedure looks like in detail.

• Step 1 . The Bureau of Immigration, Protection of Refugees and Citizenship (Immigration, Refugees and Citizenship Canada, IRCC) using Microsoft Excel assigns each application a number in order.
• Step 2 . Each application with a serial number is assigned a random number from 100,000 to 9,999,999 using the RANDOMBETWEEN function in Microsoft Excel.
• Step 3 . The Excel spreadsheet is sorted by a column with random numbers from smaller to larger - and 10,000 first entries are selected as lottery winners.

This scheme has caused criticism from some experts. Famous expert in random number generation Professor Pierre L'Ecuyer, from the University of Montreal, the author of many scientific papers on the RNG, calls this approach very bad: "This is a very old generator, it really cannot be called modern," he. Research by Professor L'Ekyuye showed that Excel pseudo-random number generator does not pass certain statistical tests. Although for this application it is quite enough, but nothing prevents the IRCC from simply taking and using a normal modern PRNG.

Excel uses deterministic result mathematical algorithms that depend on a single seed (seed). In the case of Excel, this initial value is automatically generated by the application. If you know one number in the first step, you can calculate all the other numbers in the sequence. And something similar happened before, writes a Canadian newspaper. In 1994, IT consultant Daniel Corriveau (Daniel Corriveau) discovered this pattern in the Keno game - and won 600 thousand CAD in one evening at the Casino de Montréal gambling establishment in Montreal. He guessed 19 out of 20 winning numbers three times in a row .

The investigation revealed that the casino used the same ancient PRNG as in Excel. At the beginning of each day, one random value was chosen, and the subsequent digits during the day were numbers from this predictable sequence.

At the same time, in 1994, Professor L'Equité proposed for the deterministic PRNG the structure $$$(\ mathcal {S}, \ mu, f, \ mathcal {U}, g)$where $$$\ mathcal {S}$Is a finite set of states $$$\ mu$- probability distribution in the state space $$$\ mathcal {S}$used to select the initial state $$$\ mathcal {s_ {0}}$(seed) $$$f: \ mathcal {S} \ rightarrow \ mathcal {S}$- transition function $$$\ mathcal {U}$- the output space, $$$g: \ mathcal {S} \ rightarrow \ mathcal {U}$.

Usually $$$\ mathcal {U} = (0,1)$and the state of the generator is given by the recurrent formula $$$s_ {i} = f \ (s_ {i-1})$for $$$i \ geq 1$. Generator output $$$u_ {i} = g \ (s_ {i}) \ in \ mathcal {U}$; $$$u_ {0}, \ u_ {1}, \ u_ {2} \ ...$- a sequence of pseudo-random numbers. This is a periodic sequence, and the "period" is the minimal positive $$$j$.

The most common among PRPGs is the linear congruential method, the Fibonacci method with delays, the shift register with linear feedback, the shift register with generalized feedback. Of the modern PRNGs, the Mersenne Whirl, proposed in 1997 by Matsumoto and Nishisura, was also widely adopted. Its advantages are a colossal period (2 ¹⁹⁹³⁷ −1) and a uniform distribution in 623 dimensions (the linear congruent method gives a more or less uniform distribution in a maximum of five dimensions), as well as rapid generation of random numbers.

Professor L'Ekyuye believes that the authorities are very foolish in using the PRNG from Excel because reliable cryptographic PRNG are easily accessible and cost nothing: “Cryptographic generators are free. They are on the Internet, said the professor. “Just pick one and that's it.” It's not at all difficult. ”

However, the state committee IRCC seems satisfied with the use of Excel. In an e-mailed statement, spokeswoman Shannon Ker (Shannon Ker) wrote: “We support this randomized selection process as an adequate means of equal opportunity for anyone who wants to express interest in sponsoring their parents and grandparents.”