The Demons of MiraCL

Once upon a time, an old and experienced warrior set out on a grand quest towards assembling The Scroll of Distributed Identity Based Encryption. In his home village, he had equipped himself with his trusted weapons, said a prayer for his fallen predecessors and stepped out of the village.

Go ahead and listen to some background music while reading:

First he had to fight his way across the Plains of Emptiness. Whispering ancient mantras, he wielded his weapons to prevent the Ghosts of Void from taking his soul away from this world all the while as he was making his way towards the castle named Prototype. Six days he fought and on the seventh day he rested as the Test Suite Stream ran softly under the windows of the castle and all was well.

That was, however, not the end of the quest. After consulting the the Gods he realized that he'll have to part with his old companion. For the quest ahead of him was foretold to be completed with a different tool, a weapon so powerful and ancient, that only silent whispers about the miracles it can perform roamed the world. The warrior eagerly set out on the next part of the quest, paying little heed to searching the lore for stories about his new tool.

Alas, that put him at peril, right at the gate of his castle, where he needed to defeat a many-headed beast but he found the MiraCL could only deal with a fixed size numbers and any larger number, though named Big, would end in the weapon breaking completely and dumping filthy core dumps at him. After trying a few more times, he found he could get a warning from MiraCL that the numbers were too big but not always. He was confused. How could a number be "too big" for such a mighty tool?  Courageously, he peered inside MiraCL to find the answer but found nothing but dismay.

For you see, MiraCL is an ancient weapon, forged by the Elders long before humans walked the Earth and thus is not for a mere mortal to understand. In these times, source code comments were pure blasphemy and also memory was limited and thus The Elders decreed that only 3-letter variable names shall be used. Optical illusions, out of grasp of mere men, were abundant. Different objects with the same name appeared out of nothing and weird macros obscured his vision. Wearily, he drove the beast away and set down to meditate.

In his meditations, he saw the Lore of MiraCL in front of his eyes and quickly understood that should have been the first place to look. For MiraCL was a thing out of this world and could not be wielded by mere mortals without peril.

This also gave him the knowledge on how to combine MiraCL and the mighty Address Sanitizer, his indispensable light in the Darkness of Memory Access, guiding his step away from the gaping chasms of Segfault. To forge MiraCL together with Address Sanitizer, there are two options. One is to abolish the Assembly Script and use only pure C for summoning. To do that, add to config.h this option:

#define MR_NOASM

and omit mrmuldv.c from your build spell.

Another way to forge MiraCL and the mighty Asan allows the use of Assembly but requires the 64b system. For that, invoke the following demonic spell inside the guts of Assembly implementation file, mrmuldv.g64:

#if defined(__clang__) || defined (__GNUC__)
# define ATTRIBUTE_NO_SANITIZE_ADDRESS __attribute__((no_sanitize_address))
#else
# define ATTRIBUTE_NO_SANITIZE_ADDRESS
#endif

and bless every function in that file with that attribute.

However, this was not the end of the quest, far from it. Our warrior went back to the Prototype castle and started replacing the OpenSSL in construction with MiraCL as was foretold. He worked hard, day and night, painstakingly looking at each brick, each beam. Once everything was in place, he rested and looked at the Test Suite Stream. But what horror he saw there! The stream was not crystal clear water as it once was but a stream of pure blood, splashing around, staining the walls. What once was in harmony with OpenSSL, now was in shatters. An ancient curse in the heart of MiraCL perhaps?

The warrior had no other choice but to fight any curse because it was his destiny. And so he toiled on. He separated the stream into smaller parts, let it go through a part of the castle only. He let it test one part at a time to see the result of each. After much work, he could see which rooms of the castle left each of the little trickles crystal clear and which turned it nasty. Divide and conquer, understand parts separately and know when they work. Then you can rely on them and use them in fight to achieve correctness of larger components. He still remembered the teachings of his Temple well.

But the curse was not so simple. He saw many streams running clear but once he put them together, suddenly all individual streams turned to blood! He could go through everything, seeing nothing but harmony but on the way back from the last room, everything would be in ruin again. The warrior could not believe his eyes. How was this possible? He inspected everything in detail again until he found it. He wept for hours, for with MiraCL he has awakened an evil ancient curse, thought to be long gone from our world. The Curse of Shifting Global State. Indeed, somewhere, somehow, MiraCL would shift and make all his work worthless.

But he persisted, as was foretold. He knew the curse had to be stopped. Covered in bloody mud, he rose again, the flaming sword of Divide & Conquer in his hands. Unresting, he slashed and slashed through. He found the time and place of the shift. He watched the shift occur. It was a call to powmod() which, behind his back, changed everything in the castle into ruin. The warrior couldn't believe what was happening. The powmod() function looked like a little harmless bird at first. Who would imagine it causing such a havoc? And yet, it managed to trash the whole building. Such was the Curse of Shifting Global State.

He waded through the misty Source of MiraCL, doing his best to decipher hidden meaning and ignoring any illusions of obfuscated C. There he saw that powmod() partners with prepare_monty() in its evil deed of changing a global parameter. That parameter was, however, crucial for the representation of his elliptic curves. When changed, the curves would collapse into singularity.


powmod() assumes that numbers use a Montgomery n-residue representation with a constant modulus. That was the case for objects of type G2 (an elliptic curve point) that are used in our app. Calling powmod() with a different modulus will change the global Montgomery settings and quietly break any existing instance of G2.
Cleansing himself from the effects of this sin required much meditation, but eventually clarity descended on him and he saw that MiraCL can only deal with a single modulus in the whole computation. Alas, he needed to work with different moduli and that was why The Elders sent a curse upon him. This curse was too great; the warrior had no choice but to masterfully avoid it. He locked powmod() in a chest and buried it meters underground in a stone grave. After finishing this hard labour, he seeked for a replacement. Destiny was generous with him for another function, power() turned out to be safe and powerful enough for his purpose.

Our warrior felt much lighter once this burden has been taken off his chest. Walking through the castle, with crystal water returning back to its stream, he felt in a bliss. And then he stumbled and fell down a few broken stairs. These stairs were also coming from MiraCL, they were the Big.operator+=(). Are they cursed too? They caused him to crash, only thanks to mighty Asan did he didn't suffer much pain. There were many other stairs in the castle, how come only these were so treacherous?

This time he chose to unleash the Watchdogs of LLDB on this issue and they led him right to the tapestry on the wall that was not present anywhere else. The tapestry was named otstr()
 and it displayed many numbers in hexadecimal, unfortunately it also unleashed the potential to crash in the stairs. It was a very dangerous overlook from The Elders.

It has turned out that a hashing function in code for IBE was implemented in a careless way, causing overflow of the Big type. It relied on the fact that such overflows are normally detected and avoided. Unfortunately this detection could be turned off as was done in otstr(). The otstr() function never enabled overflow checking again, an obvious bug. Watchpoints in LLDB were able to help detect places where mip->check was changed.

All of this made the warrior suspect the MiraCL, but wise as he was, he remembered similar perils with his other trusted tools as well, mastering was never an easy task.

No, I wasn't high when writing this, just a little frustrated and this felt like fun. Maybe we should write all programming blogs like this ;-)