Security Experts:

Connect with us

Hi, what are you looking for?


Data Protection

Breakthrough in Random Number Generation Could Improve Encryption

Truly random numbers are difficult to produce. The clue is in that very description: if it can be produced once, it can be reproduced. And if a random number can be reproduced, it isn’t random.

Truly random numbers are difficult to produce. The clue is in that very description: if it can be produced once, it can be reproduced. And if a random number can be reproduced, it isn’t random.

Random numbers lie at the heart of information security. They are essential to infosec’s strongest weapon – encryption, and are used to generate the keys. The problem has always been that if an attacker can reproduce the randomness used, he can reproduce the keys, and can more easily crack the encryption. For this reason, considerable intellectual capital has been spent over the years on developing ‘true randomness’. 

The University of Texas at Austin is now claiming a breakthrough. A paper by computer science professor David Zuckerman and graduate student Eshan Chattopadhyay will be presented at the annual Symposium on Theory of Computing (STOC) in June. The paper is one of three that have been awarded ‘best paper’ status – and it has been creating excitement ever since it was published for peer review and comment on the Electronic Colloquium on Computational Complexity in August 2015.

Titled ‘Explicit Two-Source Extractors and Resilient Functions‘, it describes a method of combining two ‘weakly random’ number sequences and combining them into one truly random number. Weakly random numbers, such as air temperatures or stock market prices, can over time show predictable patterns. By definition, there is nothing predictable in a truly random number.

For more than 20 years Zuckerman has been working on a process he himself pioneered – the extraction of true randomness from a weakly random sequence. Until now, however, the process has required a truly random number, or for both numbers to be almost truly random, for it to succeed. 

No more. “This is a problem I’ve come back to over and over again for more than 20 years,” says Zuckerman. “I’m thrilled to have solved it.” The new paper now describes how you can extract one truly random sequence from two weakly random sequences.

Methods for generating high-quality random numbers already exist; but they are computationally very demanding. The new method can produce even better quality at less cost. “One common way that encryption is misused is by not using high-quality randomness,” says Zuckerman. “So in that sense, by making it easier to get high-quality randomness, our methods could improve security.” It is expected that this could improve the security of everything that demands high quality encryption, from credit card transactions to military communications.

The research is being hailed as a major step forwards in security. “When I heard about it, I couldn’t sleep,” says Yael Kalai, a senior researcher working in cryptography at Microsoft Research New England who has also worked on randomness extraction. “I was so excited. I couldn’t believe it. I ran to the (online) archive to look at the paper. It’s really a masterpiece.”

Vincent Rijmen, one of the two developers of the Advanced Encryption Algorithm (AES) points out that Zuckerman’s paper is a theoretical rather than practical paper. It “is probably important within its own context,” he told SecurityWeek; “that is, deep theoretic reflections on randomness and cryptography.” The idea that it does not, at least yet, have much practical value within cryptography, was confirmed by Professor Ross Anderson of the Cambridge University Computer Laboratory. “It’s a theory paper,” he told SecurityWeek, “and unlikely to be of much engineering interest as far as I can see.”

Written By

Kevin Townsend is a Senior Contributor at SecurityWeek. He has been writing about high tech issues since before the birth of Microsoft. For the last 15 years he has specialized in information security; and has had many thousands of articles published in dozens of different magazines – from The Times and the Financial Times to current and long-gone computer magazines.

Click to comment

Expert Insights

Related Content

Application Security

Cycode, a startup that provides solutions for protecting software source code, emerged from stealth mode on Tuesday with $4.6 million in seed funding.

Application Security

Many developers and security people admit to having experienced a breach effected through compromised API credentials.

Application Security

Electric car maker Tesla is using the annual Pwn2Own hacker contest to incentivize security researchers to showcase complex exploit chains that can lead to...

Cybersecurity Funding

Los Gatos, Calif-based data protection and privacy firm Titaniam has raised $6 million seed funding from Refinery Ventures, with participation from Fusion Fund, Shasta...

Application Security

Software maker Adobe on Tuesday released security patches for 29 documented vulnerabilities across multiple enterprise-facing products and warned that hackers could exploit these bugs...

Application Security

Fortinet on Monday issued an emergency patch to cover a severe vulnerability in its FortiOS SSL-VPN product, warning that hackers have already exploited the...

Application Security

Virtualization technology giant VMware on Tuesday shipped urgent updates to fix a trio of security problems in multiple software products, including a virtual machine...

Application Security

Password management firm LastPass says the hackers behind an August data breach stole a massive stash of customer data, including password vault data that...