OMEN
11-16-2007, 11:18 AM
Random number generator spills the beans, say academics; Microsoft says it's no problem
Israeli researchers who have reverse-engineered a critical component of Windows' encryption technology say attackers could exploit flaws to decipher secured information. Microsoft Corp. has downplayed the threat.
In a paper published earlier this month, Benny Pinkas from the University of Haifa and two Hebrew University graduate students, Zvi Gutterman and Leo Dorrendorf, described how they recreated the algorithm used by Windows 2000's pseudo-random number generator (PRNG). They also spelled out vulnerabilities in the CryptGenRandom function, which calls on the algorithm.
Windows and its applications use the PRNG to create random encryption keys, which are in turn used to encrypt files and e-mail messages, and by the Secure Socket Layer protocol. SSL secures virtually every important Internet data transmission, including information from consumers to online retailers, and from bank customers to their online accounts.
By cracking the PRNG's algorithm, Pinkas and his team were able to predict its future results and uncover what it had come up with in the past, which then let them compute both previous and future encryption keys. They also discovered multiple design flaws in the algorithm that they said could give hackers the keys to the kingdom.
One of the flaws let Pinkas calculate the keys that had already been used on a Windows 2000 machine. In effect, given even remote access to the machine, a hacker could uncover encryption keys that had been generated, and thus the passwords -- or other information -- which had been used, even if they weren't saved elsewhere on the system. "If you know the 'state' of the PRNG, it should be hard to predict its previous state," said Pinkas yesterday. "It should be like a one-way street. Going backward should be impossible. But we found a way to very efficiently predict previous states of the PRNG."
That's a major bug, and one that should not have been overlooked, Pinkas added. "It's very well known how to construct a one-way generator. The fact that the PRNG used by Windows 2000 does not provide [this] demonstrates that the design is flawed."
Another problem with Windows' PRNG, added Pinkas, is that a single peek at the current state of its calculations can expose a huge amount of information. Unlike other operating systems such as Linux, Windows only refreshes its "randomness" after the PRNG has produced 128K of output. And since a typical SSL connection between, say, Internet Explorer and a bank consumes just 100-200 bytes of output, it's possible to predict 600-1,200 different SSL connections.
"Once we get the state of the PRNG, we can simulate its future state until the generator is refreshed with new random data," said Pinkas. "But that represents several hundred SSL connections."
Pinkas acknowledged that an attacker must have access to the target PC to get a glimpse of the PRNG's current state -- the prerequisite to calculating either future or past encryption keys -- but in today's security landscape, that's no barrier.
"People are finding new ways to get administrative privileges all the time," he argued. By combining a relatively run-of-the-mill attack -- one that results in full access to the machine, such as the just-patched vulnerability in Windows' URI protocol handler -- with an exploit of the PRNG's design flaws, hackers could decrypt files or reveal secure traffic between the PC and the outside world, Pinkas said. "It should be pretty easy to do our attacks."
That's not a vulnerability, that's a feature
Microsoft downplayed the problem. "We found that there is no security vulnerability," the company said in a statement attributed to Bill Sisk, Microsoft's security response communications manager. "Information is not disclosed inappropriately to unauthorized users on any supported Windows systems. In all cases discussed in the claim, information is visible only to the users themselves or to another user logged onto the local system with administrator credentials."
Sisk then went on to justify Microsoft's position that the flaws did not qualify as security vulnerabilities. "Because administrators by design can access all files and resources on a system, this does not represent inappropriate disclosure of information."
"We got basically the same [response] when we reported our findings in May," said Pinkas, who believes that the risk is greater than Microsoft wants users to believe. An attacker does not need physical access to the PC to carry out an attack that leverages the PRNG's flaws, for example. "Once you have a way to do remote code execution, you can grab the state of the generator," he said. "Any hacker who knows the OS, could grab the state, and as I said, it's not difficult to get administrative privileges on a PC."
A Symantec Corp. researcher took a middle position. In a research note made available to customers of Symantec's DeepSight threat network, analyst Erik Kamerling called the level of difficulty of such an attack as "relatively high" even as he said that Pinkas' discovery was "an extremely sought-after tool in cryptanalysis."
"An attacker must first gain some type of privileged access to an affected machine," said Kamerling. "Then the attacker would have to run a custom application or script that reads internal RNG variables. The attacker would also need to compute pending and past state information, and finally correlate and apply this forward and backward state reconstruction with the communications emanating from the target machine. It's a complicated scenario to say the least."
But Kamerling also hedged his bets. "Any development of an automated tool or program that would accomplish the techniques in the paper would increase the severity of this discovery," he admitted.
Microsoft came close to promising that it would fix the random number generator. "We are evaluating changes to further strengthen our random number generation capabilities," Sisk said. In an earlier statement, the company had said it might include an update in a future Windows service pack.
The paper co-authored by Pinkas, Gutterman and Dorrendorf can be downloaded from the Cryptology ePrint Archive in PDF format.
[I]Computerworld
Israeli researchers who have reverse-engineered a critical component of Windows' encryption technology say attackers could exploit flaws to decipher secured information. Microsoft Corp. has downplayed the threat.
In a paper published earlier this month, Benny Pinkas from the University of Haifa and two Hebrew University graduate students, Zvi Gutterman and Leo Dorrendorf, described how they recreated the algorithm used by Windows 2000's pseudo-random number generator (PRNG). They also spelled out vulnerabilities in the CryptGenRandom function, which calls on the algorithm.
Windows and its applications use the PRNG to create random encryption keys, which are in turn used to encrypt files and e-mail messages, and by the Secure Socket Layer protocol. SSL secures virtually every important Internet data transmission, including information from consumers to online retailers, and from bank customers to their online accounts.
By cracking the PRNG's algorithm, Pinkas and his team were able to predict its future results and uncover what it had come up with in the past, which then let them compute both previous and future encryption keys. They also discovered multiple design flaws in the algorithm that they said could give hackers the keys to the kingdom.
One of the flaws let Pinkas calculate the keys that had already been used on a Windows 2000 machine. In effect, given even remote access to the machine, a hacker could uncover encryption keys that had been generated, and thus the passwords -- or other information -- which had been used, even if they weren't saved elsewhere on the system. "If you know the 'state' of the PRNG, it should be hard to predict its previous state," said Pinkas yesterday. "It should be like a one-way street. Going backward should be impossible. But we found a way to very efficiently predict previous states of the PRNG."
That's a major bug, and one that should not have been overlooked, Pinkas added. "It's very well known how to construct a one-way generator. The fact that the PRNG used by Windows 2000 does not provide [this] demonstrates that the design is flawed."
Another problem with Windows' PRNG, added Pinkas, is that a single peek at the current state of its calculations can expose a huge amount of information. Unlike other operating systems such as Linux, Windows only refreshes its "randomness" after the PRNG has produced 128K of output. And since a typical SSL connection between, say, Internet Explorer and a bank consumes just 100-200 bytes of output, it's possible to predict 600-1,200 different SSL connections.
"Once we get the state of the PRNG, we can simulate its future state until the generator is refreshed with new random data," said Pinkas. "But that represents several hundred SSL connections."
Pinkas acknowledged that an attacker must have access to the target PC to get a glimpse of the PRNG's current state -- the prerequisite to calculating either future or past encryption keys -- but in today's security landscape, that's no barrier.
"People are finding new ways to get administrative privileges all the time," he argued. By combining a relatively run-of-the-mill attack -- one that results in full access to the machine, such as the just-patched vulnerability in Windows' URI protocol handler -- with an exploit of the PRNG's design flaws, hackers could decrypt files or reveal secure traffic between the PC and the outside world, Pinkas said. "It should be pretty easy to do our attacks."
That's not a vulnerability, that's a feature
Microsoft downplayed the problem. "We found that there is no security vulnerability," the company said in a statement attributed to Bill Sisk, Microsoft's security response communications manager. "Information is not disclosed inappropriately to unauthorized users on any supported Windows systems. In all cases discussed in the claim, information is visible only to the users themselves or to another user logged onto the local system with administrator credentials."
Sisk then went on to justify Microsoft's position that the flaws did not qualify as security vulnerabilities. "Because administrators by design can access all files and resources on a system, this does not represent inappropriate disclosure of information."
"We got basically the same [response] when we reported our findings in May," said Pinkas, who believes that the risk is greater than Microsoft wants users to believe. An attacker does not need physical access to the PC to carry out an attack that leverages the PRNG's flaws, for example. "Once you have a way to do remote code execution, you can grab the state of the generator," he said. "Any hacker who knows the OS, could grab the state, and as I said, it's not difficult to get administrative privileges on a PC."
A Symantec Corp. researcher took a middle position. In a research note made available to customers of Symantec's DeepSight threat network, analyst Erik Kamerling called the level of difficulty of such an attack as "relatively high" even as he said that Pinkas' discovery was "an extremely sought-after tool in cryptanalysis."
"An attacker must first gain some type of privileged access to an affected machine," said Kamerling. "Then the attacker would have to run a custom application or script that reads internal RNG variables. The attacker would also need to compute pending and past state information, and finally correlate and apply this forward and backward state reconstruction with the communications emanating from the target machine. It's a complicated scenario to say the least."
But Kamerling also hedged his bets. "Any development of an automated tool or program that would accomplish the techniques in the paper would increase the severity of this discovery," he admitted.
Microsoft came close to promising that it would fix the random number generator. "We are evaluating changes to further strengthen our random number generation capabilities," Sisk said. In an earlier statement, the company had said it might include an update in a future Windows service pack.
The paper co-authored by Pinkas, Gutterman and Dorrendorf can be downloaded from the Cryptology ePrint Archive in PDF format.
[I]Computerworld