How did the NSA hack our emails? by Numberphile

I like to see the numberphile videos as often as they appear. I find them very interesting, but I didn't share before in this blog. This time is different.

They have talk about a field that likes me very much: elliptic curves (and a pseudorandom number generator made with them, the Dual_EC_DRBG), and the greatest point is that they have summarized in 11 minutes in a wonderful elegance:

[link to the video]

But they have not only provide an explanation for not initiated, they have pointed the key of the weakness that could have been introduced.

Update: To often I forget to write the title of a post...

Update 20140116: For further reading, I stumbled a post with a proof of concept about how this affects all the users of this algorithm. It is still a suspicion that 'P' and 'Q' has been chosen from a known 'd' and no one has calculate it, but it is that: suspicious. If you are impatient (suppose not because you are at the end of this post) or you don't wanna see into the maths, go direct to the conclusions of the post.

GnuPG launches crowdfunding campaign

Long time no see! But I've found a reason to write. Yesterday, Werner Koch has send an announcement into the GnuPG maillists: 

• A crowd-funding campaign as a way to give a new push to the project.

If you read Werner's email and/or saw the video, you may think in contribute to the project.

Universal (Hexa)Decimal Classification

Since I have started with research over elliptic curves, many papers, book and other similar stuff has been read by me to take the knowledge. But there is an issue when the number of this things get too big. How can I organize the information of those papers (or books and so) in order to get back to this information and refresh the memory contents?

Very long a go, I did a course on bibliographic search and catalogue. In this course I have learned the way that the libraries in general organizes the books in there: the UDC (Universal Decimal Classification). I've looking how can I reuse this to classify the documents I think relevant for my research.

I have set up my own main classes and also I have tried to let at least one of them vacant for further updates, that mean to extend the fields of research. Event that pretension, by today, it's full again. This means that probably I'll have to do my second refactoring of this structure, because in the past I had once already this problem.

There is another way to modify my classification to have more vacants, that is think in another base. As far as I understood, the UDC was restricted from 0 to 9 to have like only one character field. Then why not a computer scientist can think in a Universal Hexadecimal Classification (UHC)?

For the records, my current main classes and their categories:

• 0.Mathematics
• 010.Number Theory
• 020.Abstract Algebra
• 030.Information Theory
• 040.Logic
• 050.Elliptic curves
• 1.Public Key
• 101.Finite fields cryptography
• 102.Elliptic curves cryptography
• 103.Hyperelliptic curves cryptography
• 110.Cryptoanalysis
• 111.Finite fields cryptoanalysis
• 112.Elliptic curves cryptoanalysis
• 113.Hyperelliptic curves cryptoanalysis
• 120.Isogenies
• 121.Isogeny volcanoes and stars
• 122.Isogenies cryptography
• 2.Symmetric cryptology
• 210.Rijndael
• 3.Hash functions
• 310.SHA
• 320.Elliptic and hyperelliptic curves
• 4.Stream cyphers
• 5.Secret sharing
• 6.Homomorphic encryption
• 7. vacant
• 8. vacant
• 9. vacant
• A. vacant
• B. vacant
• C. vacant
• D.Computation
• D10. Distributed systems
• D20. Parallel computing
• E.Hardware
• E10.Embedded systems
• E20.Smartcards
• E30.Rfid
• F.Standards
• F01.Internationals
• F10.European
• F20.North American
• F30.Russian

Because to the uncategorised classes, I think this is full and it's the first place to start merging classes and dividing them in categories. The solution of the hexadecimal, even if I have already applied, is not fixed for ever. May some day, certain categories would be subcategories. Currently this classification contains 409 documents (papers, books, and so on). My bibtex files aren't and they should.

What this system is not complaining is how to archive the notes that I wrote in the margins on the papers I read and place in here or the marks I set labelling pages on books, and so on. But this is an issue that this tool is not useful for.

How to have a search tool on this structure and inside those documents, including the posted comments?

(more) frustraited @ work

Alba is broken like since eastern. When we come back from that shutdown at the end of March. Water cooling problems, the water flow was unstable; sponges were found in the "clean water" cooling pipes, together with other dust; a weekend instrument hang causes a temperature increase and bad quality of hoses become vulcanized (below the specs) and caused a disaster in one of the two main power supplies of the booster; a TLD wrong placed in a weird space and when an Insertion Device was moved, it bends the beam pipe blocking the beam orbit, requiring to vent and replace a section. It's like we stomp shit.

This is one of the issues in this accelerator complex, but there are others that may interact.

Panic reaches the management at the beginning of this years when 12 people announces their new positions in other institutes. If you take into account that we are 145 workers, you can realizes the magnitude of the problem. From the people that says goodbye, 8 were from the computing division (around 50) and from those 4 were from the controls section (of 14). This panic didn't mention the 1 or 2 per month that has announced that the left during the past two years.

Management has announced 3 months later the creation of a commission from work behaviour improvements. Now, in July, this commission has made the first meeting by last week.

As I mention in the previous post, another reason of personal sadness: my bosses didn't case about a worker that has been called to do a talk in the university.

I didn't write here since then. I didn't found any reason to write about software design here.

But last reason to get one step further in frustration went last week.

Starting 2 months a go, in the tango meeting, there was a request to the tango community to introduce security embedded inside the tango implementation. From the last 4 years I've been trying to start a PhD in cryptology (but too busy due to the work at Alba), and I've been getting closer and closer to the field of the RFIDs and the smartcards. During the presentation where this was requested, I thought that many of the schemas to ensure RFID can be also valid to be applied in between the communication of the agents in a distributed system, like tango.

I thought it can be interesting for Alba and the tango community, to exploit that one of the workers has a hobby in cryptology and security. In this terms I've talked to my boss.

For that, I need 3 weeks to talk to my boss (this is already one problem). During this time, I've been able to, out side working hours, explain this idea to the research group in the university (they are in another city, 150 km away). I found a great acceptance about "Ensuring Tango control system", even more I've seen enthusiasm about the idea of a PhD based on an application of all the cryptological work made by the whole group (many things about public key -specially elliptic curves- symmetric cyphers, stream ciphers, secret sharing, homomorphic encryption and field like that).

At work, the response wasn't that good. The answer was like: "do what ever you like in your free time, but this must not affect your current duties at all. It's not possible to dedicate any of your working hours in such a thing". Clearly have said, if I do a PhD, is not meaning anything for Alba at all. Ooh!! This is a very clear way to motivate a worker. For my partners, also fun when was said "if you do, others would ask to do this", what's the problem on workers training?

Went I talked to my boss, I said many time to him and have to point here, that my duties have been increase every time that a partner left. Last Friday, there was a presentation about the Alba's controls system, and when the subsystems of the machine was listed, half of the elements on that list are on my behalf (and not all my duties were there).

When I went to talk about this with my boss, I went there offering my free time to work in a industrial PhD. My proposal was not to stop doing my job and disappear for full time dedication to this, my proposal was mostly the free time, but being realistic that the brain thinks at any time. As a collaboration between the university and the industry, all the involved has to put something, specially the PhD candidate.

Well done, with this deal, the simpler solution is that Alba will not appear at all in my PhD. Or if it appears will be to be mention explicitly that they haven't contribute at all; even worst Alba's position was opposition to doing a work like that.

Generalized Rijndael, schematics

Before to enter in deep on the questions remarked in the previous post about this series, I like to post some schemas that some day would be useful.

The Rijndael symmetric cryptosystem build by iteration using a network of permutations who follows the basic shannon's properties of "confusion and diffusion". The bits in the plain text are mixes and substituted by a group of operations do by an order. To decrypt, what have to be done is to do the same things but in the opposite way. For sure, there is a key to introduce here the secret to be able to undo the encrypt operation.

Diagram 1: Flow of the Rindael encrypt/decrypt

As in the diagram 1 shows, using only 4 operations (subBytes, shitfRows, mixcolumns, addRoundKey, and its inverses). But those operations are in a certain order to maintain a set of properties.

• subBytes: word substitution, where each element in the state matrix is replaced by its inverse and an affine mapping. Operations in
• shiftRows: cyclic left shift of the elements of the i'th row by i words.
• mixColumns: column linear transformation of the state matrix, where each column is given as an element of a polynomial ring, where the coefficients of this polynomial are polynomials in .
  This polynomial ring is: 
• addRoundKey: XORed transformation between the state matrix and the round key.

Is necessary to emphasize the use of a part of the key in the 'addRoundKey()' operation. This round key is much longer than the given key to encrypt/decrypt, and the process to generate this key expansion can be described in a iterative way:

Diagram 2: Iterator schema of the Rijndael key expansion

The first 4x4 matrix (the ) is the original key given with in a structure of a matrix of elements in the wordsize (8 bits, a byte in rijndael, AES). This example is using the 128 key option but the key matrix can have more columns: To build the key expansion its the same way, but remark that "#c" represents the number of columns for the message, not the key.

To build the following columns to have each round keys, an iterator is good to see how this is made. I have tried to get an schema from other webs sites, but the ones that I found haven't convinced to me. I hope this would help to someone who search on internet for a diagram of the rijndael key expansion.

RFC 6637 and construct elliptic curves

A new request for comments is available for elliptic curve cryptography. With the number 6637 the past June 11th was announced as official. Very good news for the elliptic curves and its cryptographic implementations. 


From the first version of this standard when it was a candidate has passed a few months more than 4 years. Yes, more than 4 years to public discussion. Necessary for consensus in standard development, but much more necessary for cryptography.


The old project of the patch for GnuPG, who was already obsolete a long a go, have some relation with the final code in the GnuPG. I'm glad when I see it in the sources that I have contributed somehow.


But what about the supported curves? The mentioned standard restricts the use of only a very few of them. The supported curves are only 3, one per each supported size: from the fips 186-3 the p-256, p-384 and p-521 (the biggest 3 of the 5 in the Appendix D.1.2 "Curves over Prime Fields). They are known as the NIST curves and they are from the NSA suite b.


Yes, the standard doesn't close completely the use of other curves. There is a field in the structure of the key to specify the curve, but is not set directly the curve. What is place in the field is the curve OID. Even if the number of curves that can be listed using this Object Identifiers can be very big, it will never be as big as the existing and cryptographically valid elliptic curves. But there is hope in this issue, it wasn't like that the full time of this pre-standard process, there is a octet, the first one, who have a reserved value (0xFF) for future extensions.


Why can be so important to use as many curves as the users want? Easy, one of the biggest features in elliptic curves is the possibility to change the cyclic group where the discrete logarithm is protecting your secrets, without changing the size is because using a different curve with in the same base finite field the hardness of move an attack from the cyclic group in one curve to another cyclic group in another will be almost equivalent to start from scratch the attack over the new cyclic group on the new curve over the same finite field.


But, how can be a new curve generated? Recently in arxiv I've seen a article about this matter: "Method for constructing elliptic curves using complex multiplication and its optimizations" (July 30, 2012).


I've been working in isogenies using volcanoes and stars of them to speed up the initial way to construct a new curve (pointed in the abstract of the cited article):

1. 
2. , where and
3. If it doesn't satisfy the conditions restart from 1

But this article proposes the other way around, start finding an order that satisfy the conditions and then build a curve of this order. It's a promising idea to have a nice way to have as many curves as necessary. 


With the isogenies, I didn't found how to speed this up enough to have a new (cryptographically good) curve during the key generation (a reasonable time to not desperate the user). And even more, having the possibility to reset your key by change and old curve by a new one with out needing to create a new key, but assuring the security by a public and auditable procedure.

What is the utility of this feature of the cryptosystem reset? One that I can imagine, and can be compatible with the current standard is to have a corporative elliptic curve in the smart cards and periodically renew the curve. Knowing the path in the isogeny star, all the smart cards would be able to "migrate", but for a cryptoanalyser will be a very enormous hard work to "port" any running attack, even if the public keys are available in both curves, from the origin to the current if the path is still secret.

The most important thing in cryptology is the trust on mathematics. Giving the user 3 curves, that looks good, but only 3, is not enough. Like the S-boxes in DES, that wakes up susceptibilities, specially at the beginning, to know how they had been build (why those and not any other). Even more, giving a list of hundreds of thousands curves is neither enough because the problem is still the same.

The unique solution I see on that issue, is to give this public and auditable algorithm that allows the community to validate (or break) it that make the user confortable with the provided security.

Generalized Rijndael, a review

After a too long period of time with out working on this project I like to recover it.

I did a python implementation, that will be publish as free software (GPL) who is able to change the usual parameters of the Rijndael to work in a very different way than the 3 options of the standard. As a review:

Rijndael variable parameters:

• Number of rounds
• Number of rows
• Number of columns
• Wordsize (in bits)
• Number of columns in the key

The 3 standard sizes are: {10,4,4,8,4}, {12,4,4,8,6}, {14,4,4,8,8} and this means:

• Block size always 4x4 elements of 8 bits 128 bits
• Key size can have 4, 6 or 8 columns 128,192,256 bits
• And depending on this key size the number of rounds varies from 10, 12 or 14.

But this can be changed easily by something like: {40,2,2,8,8} and this means a Rijndael of 32 bits block with keys of 128 bits (doing 40 rounds, but this was set like this in the experiment because other small block ciphers have values like this).

But what means internally to the algorithm this change?

• A new irreducible polynomial is need for the mixColumn() transformation, because the polynomial ring have the same number of coefficients than the number of rows.

Are there other options in Rijndael to get this combination? Yes: this would be equivalent to {40,4,4,2,16} and what does this mean?

• A new Rijndael SBox must be build: the original is made to apply a substitution of works of 8 bits.

Pending demonstrations:

• Is the generalized Rijndael still a Pseudo-Random Permutation (PRP)
• How to build secure SBoxes?
• How to get irreducible polynomials to be able to change the number of rows?
• Is the invertible circulant matrix also valid for polynomial rings over , with ?
• How to calculate the number of rounds necessary? Not less than need to be insecure, but not more to do superfluous calculations.

Generalized Rijndael, an approach

Following the idea of the first post about a Generalized Rijndael, I have started an implementation with some constants of the standard implementations becomes variables.

An schematic for the Rijndael would be:

This operations uses a state matrix, it's the data structure who receives the transformations during the (de)cipher process. This state matrix, in the AES, contains words of 8 bits in a 4x4.

First of all the input (of 128 bits) is cut in this basic words of 8 bits:

There are two ways to modify the size of the input: change the size of the matrix or change the size of the word. Following the article Small Scale Variants of the AES, the two options to reduce the input size from 128 to 32 bits under a Rijndael model:

• Reduce the state matrix to 2x2 (in the AES is 4x4)
• Reduce the word size to 2 bits (in the AES is 8 bits)

But, what's the best way? And there is another question, how big would be the key?

In the AES there are 3 options: 128, 192, 256 bits:

This matrix will be the input of a keyExpansion() function to have the segments of this key to be used in each part of the rounds. 

Why this sizes? Like many of the times, the choice of this 3 sizes corresponds to standardisation reasons like set a small but enough number of them to choose. The original Rijndael supports much more options: you can set a key of 512 bits and structure it into 16 columns in the key matrix. Even 1024 bits key, with 32 columns, the key expanded will still be 44 elements if the number of rows and the number of rounds are still the same.

Furthermore, with a 128 bits block of plain text and key (matrix 4x4 and word size 8) there would be 40 rounds instead of 10. In this case the key expansion will have 164 elements instead of the 44 of the standard. (the number of elements in the key expansion is #columns*#rounds) 

But how to define this parameters in the good direction? Can be the number of rounds be less with in a safety way? Or can some day be necessary to increase this number?

The Rijndael have a good performance over 32 bit hardware. The word size of 8 bits together with the 4 rows who gives 32 bit operation in the ring: . But in deep, the most powerfull feature of the Rijndael from the computation point of view is that it works in the very basic and that means binary.

I hope I'll write soon answering this questions.

Generalization of Rijndael, an introduction

Long time a go I have received a request to prepare a system to encode some data in barcodes. I thought in two options: symmetric cryptography or hash algorithm. But, there where two requirements: "non collision (in between the same key)" and "recover information from the code". Then the choose is made, they can only complained by the symmetric algorithms.

The first symmetric algorithm was to simply operate with an xor operation. But this, as a Vernam type algorithm, is more to a stream ciphering or a one-time pad. Basically means is not the correct algorithm if a key is used more than one time.

To think in the block symmetric algorithms, the old DES, the new AES or any of the finalists in the trial are candidates. I have decided for the Rijndael, the winner of the AES contest. Usually the input/output size on the symmetric algorithms must be as big as possible because the data to cipher is much bigger. For example, in the implementations of the public key cryptosystems is usual to do a hybrid system, and the data is very big. Usually the problem on the symmetrics is to interlace the blocks to avoid patterns between them.

One of the goodness of the Rijndael is the capacity of extension, bigger of smaller. The state matrix, in the standard is 4x4, but the number of rows and columns can be changed. Even more, they can be different between them. The word size, is 8 bits (having operations in 32 bits because 8 bits * 4 elements in a column), but it's possible to do Rijndael with different word sizes.

In the application about I'm working the block size will be below 128 bits, but is not fix having the idea of 64 bits block size. DES is 64 bits block (54 bits effective key size). But why to use a replaced algorithm having the possibility to adapt the Rijndael? Even more, with Rijndael the key size can be also adapted to the needs. But in crypto, any modification must have a previous process of deep think, and a post-process of forever-think.

The Triple-DES was an extension to make bigger the key sizes like 112 or 168 (56 plus 2 or 3 of the simple-DES), and there is an extension for the AES with the name AESWrap (the rfc3394), what can be thing like a sextuple-AES.

There is a difference between DES and AES, and between Triple-DES and the AESWrap. The Rijndael is not only using the key, is also doing an expansion of this key to have more bits as a key. Furthermore, the AESWrap is doing a key derivation function to introduce more dispersion and confusion.

Lets go in the first step of this project: A Generalization of Rijndael to have the data block size parametrizable, also the key size and the number of rounds.

Lets start from the simplification, how to do an Small Rijndael Variant? I have found two articles very helpful on that task:

• Mini Advanced Encryption Standard (Mini-AES): A Testbed for Cryptanalysis (2002) by Raphael Chung-wei Phan
• Small Scale Variants of the AES (2005) by C. Cid , S. Murphy , M. J. B. Robshaw

One book for cryptography developers:

• Cryptography for Developers by Tom St. Denis

And the mandatory books for Rijndael:

• AES Proposal: Rijndael (v2) by Joan Daemen, Vincent Rijmen
• The Design of Rijndael AES - The Advanced Encryption Standard  by Joan Daemen, Vincent Rijmen

Elliptic curves in the master branch of GnuPG

A few days a go, a branch for elliptic curves support un GnuPG has been announced, and I wrote here 4 words about this goal.

This month the branches has been merged to the master. First in the libgcrypt, and the next day to gnupg, and the mail thread is long with some "congrats" words. Is a really good thing to have this implementation available for the general usage.

By now, this keys are only available for "--expert" usage, and it must be like that. This is one of the steps to have them accessible for all of us and have this type of keys and algorithms used in the day by day. A cryptographic development has to follow a process of audit before an official release, and even that I should be audit forever.

This is not a lack of confidence with the developer (perhaps a bit, no worries, it's only crypto-paranoia) but the trust in the algorithms and the implementations below the secrets we put in must require a level of revision. Is not the same problem, if a program fails and some system is not accessible for a couple of hours, than if your private mail communication (ciphered) becomes compromised and some who you don't like can read them.

Elliptic curves with a git repository

Good news, finally someone found time to do what has to be done asap, with the development of elliptic curves in the field of the free software.

Also the repository of the GnuPG has been successfully migrated to git (human readable in wikipedia), great. (good and short howto)

I have not enough time for the full development of the ecdh development and I feel really glad that some one founds it. Now is time for help in test.

Great job Andrey!

To work with the git sources, 5 projects must be cloned:

$ git clone git://git.gnupg.org/libgpg-error.git

$ git clone git://git.gnupg.org/libksba.git

$ git clone git://git.gnupg.org/libassuan.git

$ git clone git://git.gnupg.org/libgcrypt.git

$ git clone git://git.gnupg.org/gnupg.git

Then go the the branches for the elliptic curves:

$ pushd libgcrypt

$ git checkout ECC-INTEGRATION-1-5

$ popd

$ pushd gnupg

$ git checkout ECC-INTEGRATION-2-1

$ popd

Now you have the sources of the GnuPG with elliptic curves support.

Update:

$ libgcrypt-config --version

1.6.0-git8993868

$ libgcrypt-config --algorithms

Symmetric cipher algorithms: arcfour blowfish cast5 des aes twofish serpent rfc2268 seed camellia

Public-key cipher algorithms: dsa elgamal rsa ecc

Message digest algorithms: crc md4 md5 rmd160 sha1 sha256 sha512 tiger whirlpool

$ gpg2 --version

gpg (GnuPG) ecc 2.2.0-git5761a9b

libgcrypt 1.6.0-git8993868

Copyright (C) 2010 Free Software Foundation, Inc.

License GPLv3+: GNU GPL version 3 or later

This is free software: you are free to change and redistribute it.

There is NO WARRANTY, to the extent permitted by law.

Home: ~/.gnupg

Supported algorithms:

Pubkey: RSA, ELG, DSA, ECDH, ECDSA

Cipher: 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH, CAMELLIA128,

CAMELLIA192, CAMELLIA256

Hash: MD5, SHA1, RIPEMD160, SHA256, SHA384, SHA512, SHA224

Compression: Uncompressed, ZIP, ZLIB

how (software) patents can bother your development

Yesterday, I receive an answer from Jivson (the author of the 'ECC in OpenPGP' internet draft) from a couple of mails discussing something about how to play with the standard to made easy some future improvements.

I'm working in an improvement of the eccGnuPG project to add the feature to reset the cryptosystem using isogeny stars like Er Rostovtsev, Anton Stolbunov propouse.

To create this isogeny stars can be usefull that they have a cofactor 2 (or at most 4, like the standards recomend) in order to have easier ways to compute a path in the stars. My surprice arribes when Jivson draws me the attention on the point that cofactor division is under a patent.

I trust on it, but I cannot find this yet. Maybe this idea with I'm working now, will be patented by someone else some day. And I can be obligated again to drop some work because an stupid patent. This is the third time that patents bother my work on elliptic curves.

This is incredible, simply unacceptable.

Repository mirroring

This post title contain the necessary words to find a solution to the problem that I post at the beginning of this month. After some try touching what was not think to be touch (the files in the .svn directory of a checkout) I decide to send an email to the users list.

Why I didn't send it before? Easily I receive a feedback indicating me that I am trespassing the limits of the things that the users should be allow to do. Then I explain not only the intentions, and more the reasons why I want this feature. And a fast answer appears!

Yes, a tool to help what I want exist, and its name is svk! I'll use it and reflect the impression. Really thanks to Ryan Schmidt.

The project starts

The meditation time is over. The alpha sources of the branch 0.9 of the elliptic curve project has been upload to my svn repository. I say 'my' because this development files are not public until it has something useful to be publish. Many things are changing in the sources from the last 0.3 branch (that never saw the light).

I have a friend who sometimes says when we write code, we make bugs, as less code we write less bugs we make... I am completely agree with he, and this is one of the ideas that comes in the 0.3 branch: try to have the same code in the patch for the GnuPG 1.4 branch than the code that the libgcrypt 1.4 has.

Between them there are some differences, but the biggest ones has to be solve by the precompiler. Others can be solved by declarations. But the most important improvement that this merge has is the split of the code in different files. The first version was think to have everything together, in one file; now the cryptographyc code will live in the cipher directory, and the mathematic code in the mpi directory (at the end the operations between point are solved by low level operations over finite fields).

After the brainstorming did here, the best option, and the most pracmatic is to implement the Internet Draft for the ECC in OpenPGP.

Quantum cryptoanalysis

By Schneier, I read a nice article about how hard will kick the quantum cryptoanalysis.

Specially is interesting for me the the post says, about RSA 4096-bit key, "if you want something stronger, you should shift to elliptic curve".

Why this sentence? I think is the reason of our current work (an article is coming soon). If one cryptoanalyst is working against you, and you have this 4096 key, your only choose is to revoke this compromised key and generate a new one larger. But over elliptic curves, only giving a new curve (over the same finite field or another) this hypothetical quantum cryptoanalysis has to be dropped and restarted.

Further more, having a base curve over the one you can describe isogeny volcanoes (bigger enough volcanoes). We are working on a cryptosetup reset in order to move your key to a new place (a new ciclic group where your ECDLP will live) where your hunter will be annoyed because all their computations has to be forget and restarted...

Secret sharing

Before to write about the possible implementation of elliptic curves over fields of characteristic 2, I want to propose another option: do some implementation over multi-public-key cryptography. This is if you have a secret that can not be trusted in only one person you can divide your secret in parts and give only one to one person. But under one reconstruction of this secret, you need all the people present.

If the secret that I said before is divided using a (n, t)-threshold scheme then your secret is shared between n players, but it can be reconstructed with t survivants from an attacker conspirator (this becomes from the thriller films).

You can create schemas with all the combination that you imagination gives. If you have a group of 10 people with a two heads, and two subgroups of four; and what you want if to have present two people of each subgroups and one of the heads (at least) you should have an schema (3-3)-threshold for the main secret and this keys to the shared secret will be re-shared as a (2-1)-threshold for the heads, and 2 (4-2)-threshold for each subgroup.

In Barcelona there are people working in this things. I meet some of them in some congresses and they are really nice people. For a long time, the secret sharing schemas have had charm for me. Could be interesting to implement this over embedded systems...

Libgcrypt

As a continuation of the yesterday brainstorming, I want to write something more about the research project. Today I will think about what can make to contribute in the libgcrypt. In this library, the ECDSA that I did in my last research project, was rewritten. This was the objective of the project, to contribute in the free software.

It is necessary to do somethings in this library. The file 'cipher/ecc.c' contains a TODO list with the necessary improvements that this library needs:

• If we support point compression we need to decide how to compute the keygrip - it should not change due to compression.

• In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a special case in mpi_powm or check whether mpi_mulm is faster.

• Decide whether we should hide the mpi_point_t definition.

• Support more than just ECDSA.

In my opinion, a research project can not be the solution of one of this points. If the research project goes in this direction, the two first points needs to be solve and the third needs to be decided.

How the project was adapted to the libgcrypt? The patch from it comes was written in a monolithic file in the way to do as less modifications as possible in the gnupg (in the 1.4 branch).

Then Werner made a good work moving the particular elliptic data structures to 'src/mpi.h' maintaining in the cryptofile 'cipher/ecc.c' the ones that have a direct relation with the pub and the private keys. Then, there are another file 'mpi/ec.c' that have everything about the mathematics background. But, in my opinion, this have one problem: the elliptic curve discrete logarithm problem (ecdlp) can be brought over primary fields (F_p) and also over fields of characteristic 2 (F_{2^m}), and this file should be split in this two mathematics bases.

This last paragraph propose another possible research project, that is implement what we had over primary fields but over characteristic 2 fields...

Elliptic curve isogeny

A few days a go (the 9th of November) a new patch about elliptic curves on GnuPG had been published. With two month delay since Mikael sent the code to me... As I read in the esr's book this is long longer time than acceptable.I'm sorry.

Now it's time to retrieve the projects. It is necessary to recuperate the gumstix development and also this year I will do my master degree research project. Against about elliptic curves. But what I said is really generic. I have some ideas, that I wanna write in this blog to be used as a brain storming to specify what is able to do and discard something else. Today is the turn elliptic curve isogeny.

Without speak on mathematics, and as far as I know, if you have a cryptoanalyst against finite fields and your paranoia says you that your privacy could be compromised, the only option that you have is increase your keylength... Use a bigger RSA or ElGamal key. Over elliptic curves you have one option before this: you can change the elliptic curve (and propose the elliptic discrete logarithm problem over a complete new one field). Nothing that the cryptoanalist computes for the old field can be used here.

But the cost to generate a new curve every key generation is hard. There are too much proprties and characteristics to test and be sure that this curve have good cryptographyc properties. One way to generate a new curve with a guarantee that it has cryptographyc characteristics is to perform some isogeny transformations to one curve that you know that it has this properties.

There exist algorithms to obtain a graph where the nodes represents elliptic curves and the edges represents an isogeny transformation. I don't need to go so far to know about isogenies, in the same university research group with I am studying they are specialists on this. For a long time a go I am listening conversations talking about this transformations an its advantages. The data structures that this isogeny transformation creates receive the name volcanus, and a join of volcanus receive the name of cordillera.

But! If the attacker knows the steps that you did in the volcanus to obtain your new isogeny curve, and it has good knowledge on isogenies transformation, it is possible to 'migrate' all the computation work that before I said that should be not useful, to the new field and continue the attack. This means that the isogeny could only generates more work to the attacker but it maybe doesn't improve the security.

An option, is to perform the transformation in secret. Generate a way in the volcanus during the key generation, from then you use the new elliptic curve and forget the relation with the one from it came... If the attacker is not able to stablish the path from one to the other, the system is secure.

Long time a go I was talking about this with Mikael, and he shows me that there are many people in the world that propose to use a public key isogeny cryptosystem, where the secret key is precisely this path in the volcanus.

Then the question is: Are we complicating so much the problem? In the low level we need to be careful with the AES symmetric cryptoanalysis. In the centre we have to beware if some algorithm better that pollard's-rho has been discovered. An then a third front we will have this transformation that could be grateful to reset a hole smartcard cryptosystem.

Yes, it is a grate thing to have the possibility to reset a institution smart card system without increase the keylength but with a restablishment of the security against an attacker.

Broadening my intentions...

My intention is not to write every day, but always when you begins a project have this illusion then, today I want to write something. Like in the first post I said I will write about the machine here I am working, also the intention to write includes my other hobby: the cryptology.

A couple of years a go, I knew a research group in my university. Since my first year there, I meet interesting people with much knowledge in so many fields, not only on science (beyond the science). The result of this relation with the cryptology and graph group, at least was my research project. But after 3 years of this project publication, Ramiro and I continue with this development, picking up the satisfaction of the official recognition attaching out work in the main branch of GnuPG.

At the beginning of this month, one article about the cipher algorithm used in this elliptic curve implementation was accepted in a Spanish symposium. The article was written in Spanish, but the problem that is treated could be much more important and this article should be translated. Yes, I can and I will do, but contributions are always accepted.

Ok, summarizing. In this blog I will not only write about synchrotron machines, I will write something about cryptography. For this subject, the close season also is open...