Sunday, June 22, 2014

Avoid incorrect ChaCha20 implementations

ChaCha20 is a stream cipher which is gaining a lot of popularity of late. Practically every library today which provides ciphers seems to have it as an addition in their latest releases.

In cryptography, there are two kinds of ciphers, block ciphers and stream ciphers. Block ciphers are where the underlying algorithm works with data with a certain fixed chunk size (or block). Popular blocks sizes are 16 and 64 bytes. Stream ciphers are effectively block ciphers where the chunk size is a single byte.

Classical stream ciphers, such as RC4, can work with data of arbitrary size, although every single byte is dependent on every previous byte. Which means encryption/decryption cannot begin in the middle of some data, and maintain compatibility where some other starting point was used. Block ciphers generally can have their blocks encrypted and decrypted arbitrarily, with none dependent upon any other, however, they cannot work with data of arbitrary size.

In order to allow block ciphers to work with data of arbitrary size, one needs to pad the data to be encrypted to a multiple of the block size. However, a clever alternative is counter mode.

Different modes for working with block ciphers exist. Some try to improve security by making each block depend on every other, some utilize various interesting techniques for other properties.  Counter mode does not encrypt the desired data (the plaintext) directly, rather, an ever incrementing counter is encrypted. The result of this encryption is then xored with the desired data.

Counter mode effectively turns a block cipher into a stream cipher, as the plaintext is never actually passed to the block cipher. Rather, a counter which is a multiple of the block size is used. One can always xor bytes with an arbitrary size, and since that is the only step in counter mode against the plain text, it is effectively a stream cipher. Since the underlying cipher can be a block cipher with no dependency between blocks, this kind of stream cipher also allows one to jump ahead to any particular multiple of the block size in the data, and begin encryption/decryption from there.

Now while ChaCha20 is advertised as a stream cipher, it's actually designed as a block cipher in counter mode. The internal design mostly mirrors that of typical counter mode design, except that the counter components are directly fused with a large but simple block cipher. Since it's really a block cipher, it has an internal block size, and also allows one to jump ahead to some multiple of it.

Since ChaCha20 is considered to have a great level of security, and all these other wonderful properties, it's starting to see a lot of use. However, practically every implementation I'm seeing is either utterly broken, or has some ridiculous API.

Common ChaCha20 implementation mistakes:
  • Implemented as a typical block cipher, not allowing usage with arbitrary amounts of bytes, or worse, the API allows for it, but produces incorrect results.
  • Implemented as a typical stream cipher with no way to jump ahead.
  • Failing on Big-Endian systems.

The first mistake I listed is the most common. If some software is only using ChaCha20 internally, and always using it in a multiple of its block size (or it's all the crummy API offers), then things are fine. But if it's a library which is inviting others to use it, and it can be used incorrectly, expect disaster to ensue.

The reference implementation of ChaCha20 was designed that an arbitrary amount of data can be encrypted, as long as all but the last usage of the API was a multiple of the block size. This was also mentioned in its documentation. However, practically every other implementation out there copies this design in some way, but makes no note of it. Worse yet, some libraries are offering ChaCha20 with this implementation flaw alongside other stream ciphers with an identical API whereas those can be used arbitrarily throughout.

Essentially, this means if you're using ChaCha20 right now in a continuous fashion with chunks of various sizes, your data is being encrypted incorrectly, and won't be interoperable with other implementations. These broken implementations are able to output exactly one chunk correctly which is not a multiple of the block size, which destroys their internal buffers, and screws up every output thereafter.

I noticed a similar situation with hash algorithm implementations several years back. However, most hash implementations are fine. Yet with ChaCha20, practically every implementation I looked at recently was broken.

Since this situation cannot stand, especially with ChaCha20 gaining speed, I am providing a simple implementation without these flaws. This implementation is designed to be correct, portable, and simple. (Those wanting an optimized version of this should consider paying for more optimized routines)

Usage of the C99 API I designed is as follows:

Custom type: chacha20_ctx
This type is used as a context for a state of encryption.

To initialize:
void chacha20_setup(chacha20_ctx *ctx, const uint8_t *key, size_t length, uint8_t nonce[8]);

The encryption key is passed via a pointer to a byte array and its length in bytes. The key can be 16 or 32 bytes. The nonce is always 8 bytes.

Once initialized, to encrypt data:
void chacha20_encrypt(chacha20_ctx *ctx, const uint8_t *in, uint8_t *out, size_t length);

You can pass an arbitrary amount of data to be encrypted, just ensure the output buffer is always at least as large as the input buffer. This function can be called repeatedly, and it doesn't matter what was done with it previously.

To decrypt data, initialize, and then call the decryption function:
void chacha20_decrypt(chacha20_ctx *ctx, const uint8_t *in, uint8_t *out, size_t length);

For encryption or decryption, if you want to jump ahead to a particular block:
void chacha20_counter_set(chacha20_ctx *ctx, uint64_t counter);

Counter is essentially the number of the next block to encrypt/decrypt. ChaCha20's internal block size is 64 bytes, so to calculate how many bytes are skipped by a particular counter value, multiply it by 64.

In addition to just providing a library, I gathered the test vectors that were submitted for various RFCs, and included a series of unit tests to test it for correctness.

For fun, since I'm also playing around a bit with LibreSSL these days, I wrapped its API up in the API I described above. The wrapper is included in my package with the rest of the code, however it is currently not designed for serious usage outside of the included test cases.

Since I already whipped up some unit tests that anyone can use, I'll leave it as an exercise to the reader to determine which libraries are and aren't implemented correctly.

I tried to ensure my library is bug free, but I am only human. If you find a mistake, please report it.


circulos said...

I was trying your test.c ... nonetheless, surprisingly, it produces this output with gcc version 4.7.0 (mingw32) on Windows:

Test Vector: Keystream #1: Success
Test Vector: Keystream #2: Success
Test Vector: Keystream #3: Success
Test Vector: Keystream #4: Success
Test Vector: Keystream #5: Failed
Test Vector: Encipherment #1: Success
Test Vector: Encipherment #2: Success
Test Vector: Encipherment #3: Failed exact length


Nathan Zimmerman said...

I had the same result... I assume they all were suppose to pass? Any idea what the issue is? I've had issues with other CHaCha implementations so I wanted to try this one out.

insane coder said...

That's weird, it's passing here, and may be due to compiler differences. I'll see what I can do.

CCoder said...

The cipher works all right but sscanf() sucks on win32. Here is a replacement for hex converter in test.c:

void hex2byte(const char *hex, uint8_t *byte)
/* win32: sscanf("%2hhx") sucks => always writes full word/LE */
while (*hex) { /* patched */
uint8_t b[4]; /* patched */
sscanf(hex, "%2hhx", b); /* patched */
*byte ++ = b[0]; /* patched */
hex += 2; /* patched */


HALIK said...

the famous of philppine tv shows is the pinoy lambingan pinoy tambayan pinoy ako pinoy teleserye pinoy tv channel pinoy tv replay pinoy flix tv.
pinoy tv tambayan

Anonymous said...

Students from different parts of the world rely on our service, as we are providing secure payment gateways, confidentiality agreements and financial aid centers for communication. Homework Help Sites

Nathanael Gray said...

Are you interested in updating your implementation to comply with ? I have a patch which I believe is doing the right thing (mostly just expanding the nonce to 12 bytes instead of 8) and updating the test vectors, but not sure where I would send it...

Assignment Help said...

Assignment Help Online services are the best way to complete academic papers without hampering your studies. Make the best use of your time using online assignment writing even if you are in the US. Get the support of native academic writers by getting the assistance of online tutors.
Online Assignment
help with my assignment
Help Assignment
Assignment Help Company

James Marcus said...

Wow, Great blog and lovely post. The way you have chosen it and the way it is written, it is very good indeed. So please write some more related to this. I am your regular reader and I am also here for my website promotion. Whenever you need to Outlook Support and you want it from experts then contact us from our Outlook Support Phone number or Outlook customer Service Number . The outlook is an email application, which is used to send and receive emails.
Outlook technical Support Phone Number
Outlook tech Support Phone Number
How do I contact outlook by phone?
Microsoft Outlook Support
Is there a phone number for Outlook support?
Microsoft Support

Help Assignment online said...

Do you have difficulty in writing an law assignment help ? Here
is the solution! law assignment help provides assignment help
services at reasonable prices to students across the globe.
If you need expert help for your law work, visit the website
Diploma assignment help or talk with the academic expert for more clarification

commerce assignment help

MBBS in Philippines said...

UV GULLAS COLLEGE OF MEDICINE is one of Top Medical College in Philippines in Cebu city. International students have the oppertunity to study medicine in phillipines at affordable cost and world class University. The college has successful alumni who have achieved well in the fields of law, business, politics, academe, medicine, sports and other endeavors. At University of the Visayas, we prepare students for a global competition.

Direct MBBS Admissions Open: 2020-21
Mobile No: +91 90329 55688
Apply Now:

customerservicehelpnumber said...

Your blog is really awesome and I really enjoyed it. Please post some other blogs. I have read out your blog post but I am here for the performance related to HP printers. I have gone through some untouched facts that are helpful to notice the problem in the concerned part. The main attraction point of view in this content is that it brings forward some facts that are worthy to trace down the burning problem in HP printers. They do not leave any stone unturned to get rid of complicated issues. But, this instruction is beneficial for those who know the fundamentals of the computer and hardware. If you feel helpless to figure out the cause of the problem, then you can take the help of the HP Printer Support team. They will help you a lot to take the full advantage of your hardly earned machine to fetch output. Visit our given links for information of HP Support:
HP Printer Customer Service,
HP Printer Tech Support,
HP Technical Support,
How do I troubleshoot my HP printer?,
Does HP have a customer service number?,
Where is the HP Support Assistant?
We are happy to help, so always feel free to contact us.
Thank You.

Geniusadda said...

Benificial for Ibps po, Clerk, SBI clerk, PO, RRB PO, Cler and Other Competitive Examination
English Comprehension 2020

Geniusadda said...

What is Bitcoin & How to Buy Bitcoin

Geniusadda said...

Thanks for shairing this information
Statutory and Regulatory Provisions

Veronica Kate said...

The blog written is extremely impressive, with a great topic. However, a bit more research could have strengthened it even further. You can explore the services as offered by, a premium academic writing services platform offering the best of Harvard Referencing Generator teamed with knowledge and experience.

James Martin said...

Under Assignment Help Online Jordan services, you will get the assistance of professional academic writers in a just few clicks. Experts will get you complete papers on the requited time if you choose to use Online Assignment Help in Jordan.

Alex Kim said...

Professional Translation Services Singapore is most preferable translation services in Singapore to get PR document translation. Here, we have a great team of high experienced and capable translators who always ready to deliver you an effective, rigorous translation into desired language.

Author said...

its a great article !!!!!!!!! JobAlert247 A Job Alert Website

MovieRulz Best Movie Download Website

assignment essay help said...

High quality economic Assignment Help at highly competitive rates. Get microeconomics assignments prepared by highly qualified professionals and score high grades on all your assignments.

Mark Henry said...

On Yes Porn Please you will discover each day the assortment that we propose to transfer the best pornography motion pictures on the net for you to appreciate, alone or as a team, or in a gathering ;) as you favor we leave it to your decision. In the event that you return each day you will see that consistently there are numerous new recordings to watch.

Digital Vishnu said...

This is incredibly useful information!! Excellent work. All is very fascinating to learn and simple to grasp. Thanks for sharing such great info. Keep Post These kinds of Articles in the future.

Digital Marketing Course in Coimbatore
Digital Marketing Course Training in Tirupur
Digital Marketing Course Training in Madurai
Digital Marketing Course Training in Theni
Digital Marketing Training in Coimbatore

abc assignment help said...

ABC Assignment Help is the most recognized and preferred one stop solution for students to get professional assignment help in any subject in Australia. Contact us now to connect with our experienced writers and score outstanding grades in your concerned subject.

Assignment service provider said...

Students in Malaysia can get our assignment help online from experts who have years of experience and knowledge in curating top-notch quality assignments from students across the world. All we professionals have high qualifications such as a Ph.D. or master's degree from renowned colleges and universities worldwide. They know what the university or college guidelines demand, and accordingly, they composed the assignment for students to get top marks and improve their overall grades. We make sure to provide our assistance at a low cost so that it is accessible to all with no hassle!

Henry Jones said...

Hey this is cool and nice share for me as well as the people who are depressed for not getting the assignment help services on time and should be worried from the people whoa re rich enough to get that easily and accordingly. Thanks for this ultiamte share that includes assignment help Canada services at even fair deals.

For more information - Check out - assignment help