Thread: [Mixmaster-devel] mixmaster's 1024-bit RSA is getting old
Brought to you by:
weaselp
From: <li...@no...> - 2013-10-29 02:15:20
|
Mixmaster has long used 1024-bit RSA with a packet format that allows a maximum of 20 hops; each encrypted with a different RSA key. The data for each hop occupies 512 bytes. Given the declining protection offered by a key size from the 1990s I decided to investigate adapting mixmaster to use 2048-bit keys (each in a larger header block) at a cost of reducing the longest chain to 10 hops. It turned out possible to exceed this goal. By using a header of 1024 bytes (max 10 hops) new code can use key sizes of 2048, 3072 and 4096 for RSA. E.g. 10 hops of 4096; or 2 of 1024 and 9 of 4096. (Key generation might be "mixmaster -G --size=4096 --lifetime=90".) The default size in the new code is 2048 bits. The RSA encryption transferred a 3DES key of 24 bytes and otherwise contained a lot of free space. Taking advantage of this space to transfer extra data without growing the packets enabled further progress. When using the larger RSA keys (2048 and up) the symmetric crypto of 3DES CBC is augmented by adding AES-256 CFB on top of it. And three parts of the data are covered by HMAC-SHA256 (in the order encrypt then MAC). - the body which previously had no protection - the current header block which had only MD5 - the next header block to prevent a tagging attack (see footnotes) When using 1024-bit RSA these new features are not used so as to keep compatibility with older software. Stats are kept of the RSA key sizes used to help operators monitor uptake of larger keys and assess when 1024-bit keys can be discontinued. Actions: 1. To review and discuss the code please use Mix...@li... (still a useful place to hold discussion although the SF maintainers are inactive ). 2. To discuss testing and deployment use Re...@li... (it would be helpful to have some short-term test remailers even if they were not to remain long term.) Some traffic may be relevant on both those lists and maybe also cry...@me... . 3. Development of a more advanced remailer needs a lead maintainer: mix...@se... http://mixminion.net/ https://github.com/nmathewson/mixminion 4. Restore freedom to the galaxy! Code location: http://www.zen19351.zen.co.uk/mixmaster302/mixmaster-3.0.2.tar.gz SHA256(mixmaster-3.0.2.tar.gz)= a88b93ea21c42ff588db6bc506b3e6eea4e8eb666d5a90beb1dd785b7e0920ed Further reading: http://www.freehaven.net/anonbib/cache/mixmaster-spec.txt https://crypto.is/blog/packet_formats_1 https://crypto.is/blog/tagging_attack_on_mixmaster http://www.nsa.gov/business/programs/elliptic_curve.shtml |
From: Steve C. <st...@mi...> - 2013-10-29 09:51:41
Attachments:
signature.asc
|
On Tue, Oct 29, 2013 at 02:15:09AM +0000, li...@no... wrote: > Mixmaster has long used 1024-bit RSA with a packet format that allows > a maximum of 20 hops; each encrypted with a different RSA key. The > data for each hop occupies 512 bytes. > > Given the declining protection offered by a key size from the 1990s I > decided to investigate adapting mixmaster to use 2048-bit keys (each > in a larger header block) at a cost of reducing the longest chain to > 10 hops. > > It turned out possible to exceed this goal. By using a header of > 1024 bytes (max 10 hops) new code can use key sizes of 2048, 3072 > and 4096 for RSA. E.g. 10 hops of 4096; or 2 of 1024 and 9 of 4096. > (Key generation might be "mixmaster -G --size=4096 --lifetime=90".) > The default size in the new code is 2048 bits. Coincidentally we appear to have arrived at very similar solutions. I've also got a working Mixmaster alternative that uses 10 headers of 1024 bytes each. This adds support for up to 4096-bit RSA keys and maintains the same overall packet size of 20480 bytes. My spec is: Packet Info (256 Bytes):- Packet type 0 (intermediate hop): [ 9 Initialization vectors 144 bytes ] [ Next address 112 bytes ] Packet type 1 (final hop): [ Chunk number 1 byte ] [ Number of chunks 1 byte ] [ Message ID 16 bytes ] [ Initialization vector 16 bytes ] [ Padding 222 bytes ] Mixmaster currently has three Packet Types but I couldn't see the point of seperating Exit and Chunked Exit when Exit can just be a single Chunk. Encrypted Header (384 Bytes): [ Packet ID 16 bytes ] [ AES key 32 bytes ] [ Packet type identifier 1 byte ] [ Packet Info 256 bytes ] [ Timestamp 2 bytes ] [ Padding 13 bytes ] [ SHA2-512 Message digest 64 bytes ] Header (1024 Bytes): [ Public key ID 16 bytes ] [ Length of RSA-encrypted data 2 bytes ] [ RSA-encrypted session key 512 bytes ] [ Initialization vector 16 bytes ] [ Encrypted header part 384 bytes ] [ Padding 30 bytes ] [ SHA2-512 Message digest 64 bytes ] Payload: [ Length 2 bytes ] [ SHA2-512 Message Digest 64 bytes ] [ Content 10174 bytes ] This is currently only something I'm playing with so it should be easy to modify it to concur with your specification. I'm also looking at using HTTP as a transport instead of SMTP. The justification for this being that HTTP is used extensively on the Tor network. This should make it very easy to run remailers as Tor Location Hidden Services. > Actions: > 1. To review and discuss the code please use Mix...@li... > (still a useful place to hold discussion although the SF maintainers are inactive ). > 2. To discuss testing and deployment use Re...@li... (it would be helpful > to have some short-term test remailers even if they were not to remain long term.) > Some traffic may be relevant on both those lists and maybe also cry...@me... . > 3. Development of a more advanced remailer needs a lead maintainer: > mix...@se... > http://mixminion.net/ > https://github.com/nmathewson/mixminion > 4. Restore freedom to the galaxy! > > Code location: > http://www.zen19351.zen.co.uk/mixmaster302/mixmaster-3.0.2.tar.gz > SHA256(mixmaster-3.0.2.tar.gz)= a88b93ea21c42ff588db6bc506b3e6eea4e8eb666d5a90beb1dd785b7e0920ed Thanks very much for your efforts, I'll take a look and provide some feedback. |
From: <li...@no...> - 2013-10-29 23:58:57
|
Steve Crook <steve mixmin.net> writes: > Coincidentally we appear to have arrived at very similar solutions. There was a certain obviousness about the main thrust of our designs. > Encrypted Header (384 Bytes): > [ Packet ID 16 bytes ] > [ AES key 32 bytes ] > [ Packet type identifier 1 byte ] > [ Packet Info 256 bytes ] > [ Timestamp 2 bytes ] > [ Padding 13 bytes ] > [ SHA2-512 Message digest 64 bytes ] > > Header (1024 Bytes): > [ Public key ID 16 bytes ] > [ Length of RSA-encrypted data 2 bytes ] > [ RSA-encrypted session key 512 bytes ] > [ Initialization vector 16 bytes ] > [ Encrypted header part 384 bytes ] > [ Padding 30 bytes ] > [ SHA2-512 Message digest 64 bytes ] I see you've moved message digests to predictable positions at the end of each block to avoid the current mess where you need to somewhat use the block before you can check it matches the digest. I doubt 65536 different public keys sizes are needed. My guess is 4096 (only) is good for the near term and then the best recommendation will be some EC - but which one nobody may know for a while. Who knows whether in a couple of years NIST and DJB might endorse a few of the same curves? With a new incompatible alternative you have options such as a protocol version field to indicate what is coming later in the packet. > This is currently only something I'm playing with so it should be easy > to modify it to concur with your specification. I don't think an alternative needs to follow my spec which is a minimal change for easy migration. If you're aiming for a new codebase and no more 3DES then you have a new start. I think the worthwhile points to lift are: - On intermediate hops require an integrity check on the following hop as explained on Ritter's blog. - Use hashes iterated twice (as reccomended by Schneier). The style of iterations I've used is HMAC. - Encrypt under RSA data that is not a symmetric key itself but is something that hashes to the symmetric key. Then if a break against RSA leaks half your bits the search space has not been much reduced. (I think I read that in Schneier too.) - If the first design leaves space inside the RSA-encrypted data it may be useful later. > I'm also looking at using HTTP as a transport instead of SMTP. The > justification for this being that HTTP is used extensively on the Tor > network. This should make it very easy to run remailers as Tor Location > Hidden Services. HTTP(S) typically has small requests and large replies. That suggests a change from an SMTP-like model to a POP3-like model where each node would query other nodes with "any messages for me? show me one". To do this each node would have to know where to receive from (information that starts out in the client that prepares the onion packaging). So some way of introducing nodes to each other is required. |
From: Lance C. <lo...@ob...> - 2013-10-29 16:57:06
Attachments:
smime.p7s
|
This is an excellent proposal. In practice, no one uses more than a few hops for real messages. I suspect that 5 is the realistic upper limit to ensure reasonable delivery time and reliability. I really went over the top in using 20 header blocks. Roll out will be a key. One does not want client software that only has one or two servers through which it could route, nor would one want to be one of only a few few users of the new key size, since that would be easily tracked as well. -Lance -- Lance Cottrell lo...@ob... On Oct 29, 2013, at 2:34 AM, Steve Crook <st...@mi...> wrote: > On Tue, Oct 29, 2013 at 02:15:09AM +0000, li...@no... wrote: >> Mixmaster has long used 1024-bit RSA with a packet format that allows >> a maximum of 20 hops; each encrypted with a different RSA key. The >> data for each hop occupies 512 bytes. >> >> Given the declining protection offered by a key size from the 1990s I >> decided to investigate adapting mixmaster to use 2048-bit keys (each >> in a larger header block) at a cost of reducing the longest chain to >> 10 hops. >> >> It turned out possible to exceed this goal. By using a header of >> 1024 bytes (max 10 hops) new code can use key sizes of 2048, 3072 >> and 4096 for RSA. E.g. 10 hops of 4096; or 2 of 1024 and 9 of 4096. >> (Key generation might be "mixmaster -G --size=4096 --lifetime=90".) >> The default size in the new code is 2048 bits. > Coincidentally we appear to have arrived at very similar solutions. > I've also got a working Mixmaster alternative that uses 10 headers of > 1024 bytes each. This adds support for up to 4096-bit RSA keys and > maintains the same overall packet size of 20480 bytes. > > My spec is: > > Packet Info (256 Bytes):- > Packet type 0 (intermediate hop): > [ 9 Initialization vectors 144 bytes ] > [ Next address 112 bytes ] > > Packet type 1 (final hop): > [ Chunk number 1 byte ] > [ Number of chunks 1 byte ] > [ Message ID 16 bytes ] > [ Initialization vector 16 bytes ] > [ Padding 222 bytes ] > > Mixmaster currently has three Packet Types but I couldn't see the point > of seperating Exit and Chunked Exit when Exit can just be a single Chunk. > > Encrypted Header (384 Bytes): > [ Packet ID 16 bytes ] > [ AES key 32 bytes ] > [ Packet type identifier 1 byte ] > [ Packet Info 256 bytes ] > [ Timestamp 2 bytes ] > [ Padding 13 bytes ] > [ SHA2-512 Message digest 64 bytes ] > > Header (1024 Bytes): > [ Public key ID 16 bytes ] > [ Length of RSA-encrypted data 2 bytes ] > [ RSA-encrypted session key 512 bytes ] > [ Initialization vector 16 bytes ] > [ Encrypted header part 384 bytes ] > [ Padding 30 bytes ] > [ SHA2-512 Message digest 64 bytes ] > > Payload: > [ Length 2 bytes ] > [ SHA2-512 Message Digest 64 bytes ] > [ Content 10174 bytes ] > > This is currently only something I'm playing with so it should be easy > to modify it to concur with your specification. > > I'm also looking at using HTTP as a transport instead of SMTP. The > justification for this being that HTTP is used extensively on the Tor > network. This should make it very easy to run remailers as Tor Location > Hidden Services. > >> Actions: >> 1. To review and discuss the code please use Mix...@li... >> (still a useful place to hold discussion although the SF maintainers are inactive ). >> 2. To discuss testing and deployment use Re...@li... (it would be helpful >> to have some short-term test remailers even if they were not to remain long term.) >> Some traffic may be relevant on both those lists and maybe also cry...@me... . >> 3. Development of a more advanced remailer needs a lead maintainer: >> mix...@se... >> http://mixminion.net/ >> https://github.com/nmathewson/mixminion >> 4. Restore freedom to the galaxy! >> >> Code location: >> http://www.zen19351.zen.co.uk/mixmaster302/mixmaster-3.0.2.tar.gz >> SHA256(mixmaster-3.0.2.tar.gz)= a88b93ea21c42ff588db6bc506b3e6eea4e8eb666d5a90beb1dd785b7e0920ed > Thanks very much for your efforts, I'll take a look and provide some > feedback. > _______________________________________________ > Remops mailing list > Re...@li... > http://lists.mixmin.net/mailman/listinfo/remops |
From: <li...@no...> - 2013-10-30 00:17:04
|
Lance Cottrell <loki obscura.com> writes: > In practice, no one uses more than a few hops for real > messages. I suspect that 5 is the realistic upper limit to > ensure reasonable delivery time and reliability. I really > went over the top in using 20 header blocks. Good thing too provided the cost was acceptable. If you'd used 6 hops then halving it would get 3. > Roll out will be a key. One does not want client software that > only has one or two servers through which it could route, > nor would one want to be one of only a few few users of the > new key size, since that would be easily tracked as well. Ease of deployment is why I've arranged my code as I have. Remailers and clients don't need to update at the same time and anyone with the new client remains able to use all the remailers. You can always pick a 1024 remailer as a first hop if you don't want to be recognised as a user of the new software (assuming you downloaded it undetected). |
From: Lance C. <lo...@ob...> - 2013-10-30 16:29:50
Attachments:
smime.p7s
|
I like to avoid asking users to think too much. It would be ideal if there were some kind of timer or something, so it could get widely deployed before starting to be used. -Lance -- Lance Cottrell lo...@ob... On Oct 29, 2013, at 5:16 PM, li...@no... wrote: > Lance Cottrell <loki obscura.com> writes: > >> In practice, no one uses more than a few hops for real >> messages. I suspect that 5 is the realistic upper limit to >> ensure reasonable delivery time and reliability. I really >> went over the top in using 20 header blocks. > > Good thing too provided the cost was acceptable. If you'd > used 6 hops then halving it would get 3. > >> Roll out will be a key. One does not want client software that >> only has one or two servers through which it could route, >> nor would one want to be one of only a few few users of the >> new key size, since that would be easily tracked as well. > > Ease of deployment is why I've arranged my code as I have. Remailers > and clients don't need to update at the same time and anyone with the > new client remains able to use all the remailers. > > You can always pick a 1024 remailer as a first hop if you don't want > to be recognised as a user of the new software (assuming you downloaded > it undetected). |
From: <li...@no...> - 2013-10-31 00:22:54
|
Lance Cottrell <loki obscura.com> > I like to avoid asking users to think too much. > It would be ideal if there were some kind of timer or something, so it = > could get widely deployed before starting to be used. stage 1 We have to start with agreement on the change in key size. Can everybody on these lists test and examine the new s/w and either agree to use it in all mixmaster remailer installations or else state their objections here? By end November? (If anyone runs a remailer on Windows I'd be interested in the result of testing there as I haven't done any.) stage 2 Remailers upgrade the s/w but do not publish large keys yet. Then distribute the new s/w - from every site we can manage that currently has mixmaster s/w for download. And run a publicity campaign saying people need the new s/w ready for an upgrade in key size coming soon. Because of the anonymous user base this has to be a broadcast on mailing lists, newsgroups, blogs and forums. Publicity will include the error message shown by old s/w used with large keys so that anyone who misses the upgrade and googles the error message will catch on. (Throughout December?) Up to this point there's been no change in the formatting/crypto behaviour outside of testing because no large keys are in use. stage 3 At an agreed time all remailers generate 4096-bit keys and all the places publishing keys make sure to distribute them. Expiry of all 1024-bit keys follows. One week after new year? |
From: <li...@no...> - 2013-11-14 07:11:35
|
Version 3.0.2a is a small change from 3.0.2 where the default key size is now 4096 and in the stats processing a buffer is checked to ensure it is initialised before use. http://www.zen19351.zen.co.uk/mixmaster302/ mixmaster-3.0.2a.tar.gz SHA256(mixmaster-3.0.2a.tar.gz)= 1f921039148d84fb3c89bbf9a8e1637cfbf3d0e02cb0612df67f50ea569884b9 diff mixmaster-3.0.2/Src/stats.c mixmaster-3.0.2a/Src/stats.c 242c242 < if ((rs=mix_openfile(RSATEXTFILE, "r")) != NULL) { --- > if (b && (rs=mix_openfile(RSATEXTFILE, "r")) != NULL) { |