November 30, 2023

Is Ukrainian blockchain immune to a quantum computer? Fact check ForkLog

In early February, representatives of the State Service for Special Communications and Information Protection of Ukrainereported on the development of a basic blockchain system using domestic cryptography with high post-quantum strength.

However, in Ukraine, as well as throughout the world, untilPost-quantum digital signature standards have not yet been adopted. In addition, not all standards specified by specialists are stable in the post-quantum period, as was stated.

Especially for ForkLog Doctor of Engineering,Professor, Department of Security of Information Systems and Technologies, Kharkiv National University V.N. Karazina, a researcher at IOHK, Roman Oleinikov explained in detail what the listed standards are and what blockchain properties are affected by the existence of post-quantum durability.

ForkLog: Hello, Roman. Is it true at present to maintain the existence of cryptographic standards?

Roman Oleinikov:Development of post-quantum standardsasymmetric cryptographic transformations are still ongoing. There are several working drafts of new digital signature standards in Ukraine. They are aimed both at increasing the speed of transformations, also based on elliptic curves, and at ensuring stability in the face of the emergence of a hypothetical quantum computer for cryptanalysis (post-quantum signature). But none of them have been accepted as a standard.

US National Standards Institute is now alsocontinues the open competition of post-quantum cryptographic primitives, and after the second stage, nine post-quantum signature candidates remain under consideration.

That is, it is too early to talk about the standard of post-quantum signature. There are good algorithms, but they are not standardized yet.

ForkLog: In developing its blockchain system, the State Special Communications Service used four standards. Tell us about their technical characteristics.

Roman Oleinikov:StandardDSTU 4145: 2002defines generation and verification algorithmsdigital signature based on elliptic curves. This signature underlies Ukraine's modern electronic trust services, including public key infrastructure, but it is not post-quantum.

By the standards of modern information technology, DSTU 4145: 2002 already has a fairly long experience in use, but still provides the necessary properties.

But DSTU 7564: 2014, DSTU 7624: 2014 and DSTU 8845: 2019 really provide high durability in the post-quantum period.

StandardDSTU 7624: 2014defines the modern block cipher «Kalina» and its modes of operation to hide semantic content and prevent unauthorized modification of messages.

The cipher is flexible and supports block sizeand key length up to 512 bits. It is the only block encryption standard in the world that supports this level of security. In comparison, the widespread AES provides a maximum key length of 256 bits.

At the same time, in software implementation onmost modern 64-bit desktop and server platforms with the same key lengths «Kalina» has higher performance than AES.

DSTU 7624:2014 sets ten block cipher operation modes. For comparison, the international standard ISO / IEC 10116 has only six modes (they are also in the national standard of Ukraine). Additional modes provide more opportunities for Ukrainian developers of cryptographic information protection tools compared to colleagues from countries in the region and throughout Europe as a whole.

«Kalina» - a highly secure and fast symmetric cipher, aimed at modern high-performance hardware platforms.

StandardDSTU 7564: 2014hash function defined«Kupina», providing highly secure and flexible cryptographic conversion. «Kupina» It is used both as an independent standard to ensure integrity, and as an additional transformation as part of a digital signature.

«Kupina» and «Kalina»are unified, that is, they use a single set of substitutions and linear transformation matrices, which further increases the efficiency of cryptographic protection systems based on them. «Kupina», like «Kalina», uses a provable security approach when justifying properties, which is an additional advantage of DSTU 7564 over SHA-256, where such a property is absent. At the same time, ensuring provable stability leads to a decrease in the speed of transformation of «Kupina» compared to SHA-256.

Immediately after the implementation of the standards,«Kupina» and «Kalina» were published in English and presented at international conferences outside Ukraine. Independent results from researchers from Canada, the USA, Austria, India and other countries were obtained confirming the strength of cryptographic transformations. DSTU 7624 and DSTU 7564 were included in software libraries developed outside of Ukraine, for example, Crypto++.

StandardDSTU 8845: 2019defines a stream cipher.It is also focused on ensuring confidentiality, and a distinctive feature is the high speed of transformations necessary to protect backbone communication channels.

Symmetric ciphers DSTU 7624, DSTU 7564 and DSTU 8845 provide strength in the post-quantum period.

At the same time, a hypothetical quantum computer,capable of efficiently executing the Shore algorithm for the corresponding key lengths, it is a threat to the stability of elliptic curves (DSTU 4145 standard, digital signature), just as it is a threat to ECDSA, EdDSA, DSA, RSA and others. But such a device is still hypothetical for more than a decade.

US National Institute of Standards Plansthe introduction of post-quantum asymmetric cryptographic transformations only by 2024, if there are no early technological breakthroughs in the field of a quantum computer. There is a draft standard for post-quantum signature in Ukraine.

ForkLog: What gives blockchain post-quantum resilience?

Roman Oleinikov:If we consider a long-term period ofdecades, with the unpredictable risk of the emergence of a quantum computer, then the use of post-quantum cryptographic primitives will ensure stability in this threat model.

For modern bitcoin, this hypotheticala quantum computer will not allow you to spend random output (UTXO) at the discretion of the attacker. As a rule, in UTXO bitcoin is stored not the public key itself, but its hash (SHA-256 + RIPEMD-160); finding the inverse image of the hash is performed using a much less efficient algorithm.

A hypothetical quantum computer attack onmodern Bitcoin is possible in rather harsh conditions for an attacker and only for transactions that the owners themselves have already sent to the network (along with the public key), but the miners have not yet included in the block. In such a model, an attacker will have up to 10 minutes on average for cryptanalysis and convincing the miner to include in the block exactly an alternative transaction that spends the same output.

ForkLog: What are the positive and negative effects of post-quantum resilience on blockchain properties?

Roman Oleinikov:Typically, modern post-quantum primitivesless performant than elliptic curve based transformations. Accordingly, their use, all other things being equal, will lead to a decrease in throughput or an increase in the requirements for the available computing resources of the node processing and confirming transactions.

However, if we consider distributedRegisters, including blockchains, not only as cryptocurrencies, then post-quantum durability has additional advantages. It will allow for distributed data storage for decades - real estate registers, certificates of education, etc., where the main requirement is reliability, not high bandwidth.

Naturally, all this subject to resistance toattacks carried out on traditional computers (not only on a hypothetical quantum one), safe generation and storage of keys, and the fulfillment of many other necessary security conditions.

Forklog: They plan to use the domestic blockchain to create a national cryptocurrency and smart contracts, and now it has already deployed a prototype electronic voting system. How feasible are all these projects?

Roman Oleinikov:I am not familiar with the deep technical details of the State Special Communications Project, so I cannot comment on the level of its feasibility or impracticability right now.

In general, at the current level of developmentblockchain systems, there can be no problems with the declared functionality. Depending on the team involved in such a system, the implementation time and resources expended may vary.

ForkLog: Is it really necessary to use post-quantum solutions in the electronic voting system?

Roman Oleinikov:To ensure a number of important system propertiesvoting (for example, individual and universal verifiability), access to the distributed registry is necessary for each participant. At the same time, other properties (confidentiality, fairness, legitimacy) are ensured by the cryptographic scheme used.

In the case of a hypothetical quantumA potential threat to the computer is the confidentiality of the votes of the participants, even if the vote was taken 10-20 years ago (naturally, if the attacker at that time still had access to the corresponding blockchain that was visible to all the participants in the vote).

The inclusion of such a threat in the voting system, in my opinion, is appropriate.

Naturally, this increases the complexity of the project due to new cryptographic transformations, but potentially gives more guarantees of security / reliability to the voters.


Read on: When will Bitcoin be hacked, or how real is the threat from quantum computers