Connect with us

Hi, what are you looking for?

SecurityWeekSecurityWeek

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.”

Advertisement. Scroll to continue reading.

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

Trending

Daily Briefing Newsletter

Subscribe to the SecurityWeek Email Briefing to stay informed on the latest threats, trends, and technology, along with insightful columns from industry experts.

Join the session as we discuss the challenges and best practices for cybersecurity leaders managing cloud identities.

Register

SecurityWeek’s Ransomware Resilience and Recovery Summit helps businesses to plan, prepare, and recover from a ransomware incident.

Register

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.

Data Protection

The cryptopocalypse is the point at which quantum computing becomes powerful enough to use Shor’s algorithm to crack PKI encryption.

Artificial Intelligence

The CRYSTALS-Kyber public-key encryption and key encapsulation mechanism recommended by NIST for post-quantum cryptography has been broken using AI combined with side channel attacks.

Compliance

The three primary drivers for cyber regulations are voter privacy, the economy, and national security – with the complication that the first is often...

Data Protection

While quantum-based attacks are still in the future, organizations must think about how to defend data in transit when encryption no longer works.

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

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...

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...