- tor-commits - lists.torproject.org

[obfsproxy/master] Revived unit tests.
by nickm＠torproject.org 29 May '11

29 May '11

commit 9d2e98860ed5c0e5f6a6a45869a20732a0a01218 Author: George Kadianakis <desnacked(a)gmail.com> Date: Wed May 25 04:10:23 2011 +0200 Revived unit tests. --- src/test/unittest.c | 2 +- src/test/unittest_obfs2.c | 99 ++++++++++++++++++++++++++++++++++++++------ 2 files changed, 86 insertions(+), 15 deletions(-) diff --git a/src/test/unittest.c b/src/test/unittest.c index 9ca6a74..41159ca 100644 --- a/src/test/unittest.c +++ b/src/test/unittest.c @@ -15,7 +15,7 @@ extern struct testcase_t socks_tests[]; struct testgroup_t groups[] = { { "crypt/", crypt_tests }, - /* { "proto/", protocol_tests }, */ + { "proto/", protocol_tests }, { "socks/", socks_tests }, END_OF_GROUPS }; diff --git a/src/test/unittest_obfs2.c b/src/test/unittest_obfs2.c index ce743c8..052c909 100644 --- a/src/test/unittest_obfs2.c +++ b/src/test/unittest_obfs2.c @@ -1,4 +1,3 @@ -#if 0 /* Copyright 2011 Nick Mathewson You may do anything with this work that copyright law would normally @@ -32,8 +31,20 @@ test_proto_setup(void *data) tt_assert(set_up_protocol(OBFS2_PROTOCOL) >= 0); - client_proto = proto_new(OBFS2_PROTOCOL,1); - server_proto = proto_new(OBFS2_PROTOCOL,1); + protocol_params_t *proto_params_serv = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_serv); + proto_params_serv->is_initiator = 1; + proto_params_serv->shared_secret = "hahaha"; + proto_params_serv->shared_secret_len = 7; + + protocol_params_t *proto_params_client = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_client); + proto_params_client->is_initiator = 0; + proto_params_client->shared_secret = "hahaha"; + proto_params_client->shared_secret_len = 7; + + client_proto = proto_new(OBFS2_PROTOCOL,proto_params_serv); + server_proto = proto_new(OBFS2_PROTOCOL,proto_params_client); tt_assert(client_proto); tt_assert(server_proto); @@ -61,8 +72,20 @@ test_proto_handshake(void *data) tt_assert(set_up_protocol(OBFS2_PROTOCOL) >= 0); - client_proto = proto_new(OBFS2_PROTOCOL,1); - server_proto = proto_new(OBFS2_PROTOCOL,0); + protocol_params_t *proto_params_serv = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_serv); + proto_params_serv->is_initiator = 1; + proto_params_serv->shared_secret = "hahaha"; + proto_params_serv->shared_secret_len = 7; + + protocol_params_t *proto_params_client = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_client); + proto_params_client->is_initiator = 0; + proto_params_client->shared_secret = "hahaha"; + proto_params_client->shared_secret_len = 7; + + client_proto = proto_new(OBFS2_PROTOCOL,proto_params_serv); + server_proto = proto_new(OBFS2_PROTOCOL,proto_params_client); tt_assert(client_proto); tt_assert(server_proto); @@ -121,8 +144,20 @@ test_proto_transfer(void *data) tt_assert(set_up_protocol(OBFS2_PROTOCOL) >= 0); - client_proto = proto_new(OBFS2_PROTOCOL,1); - server_proto = proto_new(OBFS2_PROTOCOL,0); + protocol_params_t *proto_params_serv = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_serv); + proto_params_serv->is_initiator = 1; + proto_params_serv->shared_secret = "hahaha"; + proto_params_serv->shared_secret_len = 7; + + protocol_params_t *proto_params_client = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_client); + proto_params_client->is_initiator = 0; + proto_params_client->shared_secret = "hahaha"; + proto_params_client->shared_secret_len = 7; + + client_proto = proto_new(OBFS2_PROTOCOL,proto_params_serv); + server_proto = proto_new(OBFS2_PROTOCOL,proto_params_client); tt_assert(client_proto); tt_assert(server_proto); @@ -204,9 +239,21 @@ test_proto_splitted_handshake(void *data) struct protocol_t *server_proto = NULL; tt_assert(set_up_protocol(OBFS2_PROTOCOL) >= 0); + + protocol_params_t *proto_params_serv = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_serv); + proto_params_serv->is_initiator = 1; + proto_params_serv->shared_secret = "hahaha"; + proto_params_serv->shared_secret_len = 7; - client_proto = proto_new(OBFS2_PROTOCOL,1); - server_proto = proto_new(OBFS2_PROTOCOL,0); + protocol_params_t *proto_params_client = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_client); + proto_params_client->is_initiator = 0; + proto_params_client->shared_secret = "hahaha"; + proto_params_client->shared_secret_len = 7; + + client_proto = proto_new(OBFS2_PROTOCOL,proto_params_serv); + server_proto = proto_new(OBFS2_PROTOCOL,proto_params_client); tt_assert(client_proto); tt_assert(server_proto); @@ -346,8 +393,20 @@ test_proto_wrong_handshake_magic(void *data) tt_assert(set_up_protocol(OBFS2_PROTOCOL) >= 0); - client_proto = proto_new(OBFS2_PROTOCOL,1); - server_proto = proto_new(OBFS2_PROTOCOL,0); + protocol_params_t *proto_params_serv = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_serv); + proto_params_serv->is_initiator = 1; + proto_params_serv->shared_secret = "hahaha"; + proto_params_serv->shared_secret_len = 7; + + protocol_params_t *proto_params_client = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_client); + proto_params_client->is_initiator = 0; + proto_params_client->shared_secret = "hahaha"; + proto_params_client->shared_secret_len = 7; + + client_proto = proto_new(OBFS2_PROTOCOL,proto_params_serv); + server_proto = proto_new(OBFS2_PROTOCOL,proto_params_client); tt_assert(client_proto); tt_assert(server_proto); @@ -413,8 +472,21 @@ test_proto_wrong_handshake_plength(void *data) tt_assert(set_up_protocol(OBFS2_PROTOCOL) >= 0); - client_proto = proto_new(OBFS2_PROTOCOL,1); - server_proto = proto_new(OBFS2_PROTOCOL,0); + protocol_params_t *proto_params_serv = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_serv); + proto_params_serv->is_initiator = 1; + proto_params_serv->shared_secret = "hahaha"; + proto_params_serv->shared_secret_len = 7; + + protocol_params_t *proto_params_client = calloc(1, sizeof(protocol_params_t)); + tt_assert(proto_params_client); + proto_params_client->is_initiator = 0; + proto_params_client->shared_secret = "hahaha"; + proto_params_client->shared_secret_len = 7; + + + client_proto = proto_new(OBFS2_PROTOCOL,proto_params_serv); + server_proto = proto_new(OBFS2_PROTOCOL,proto_params_client); tt_assert(client_proto); tt_assert(server_proto); @@ -475,4 +547,3 @@ struct testcase_t protocol_tests[] = { T(wrong_handshake_plength, 0), END_OF_TESTCASES }; -#endif

1 0

[obfsproxy/master] Merge remote-tracking branch 'asn/shared_secret'
by nickm＠torproject.org 29 May '11

29 May '11

commit 9ef190a4d70cd44053dde4d19d5579a609ced091 Merge: 8ac51f3 ad09a51 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sat May 28 21:34:22 2011 -0400 Merge remote-tracking branch 'asn/shared_secret' Conflicts: doc/protocol-spec.txt doc/protocol-spec.txt | 12 ++++-- src/main.c | 38 ++++++++++------- src/network.c | 43 +++++++++++-------- src/protocol.c | 6 +- src/protocol.h | 59 ++++++++++++++++++-------- src/protocols/dummy.c | 6 +- src/protocols/dummy.h | 3 +- src/protocols/obfs2.c | 94 +++++++++++++++++++++++++++++++---------- src/protocols/obfs2.h | 9 ++-- src/protocols/obfs2_crypt.c | 4 +- src/protocols/obfs2_crypt.h | 2 + src/test/unittest_obfs2.c | 97 +++++++++++++++++++++++++++++++++++++----- 12 files changed, 272 insertions(+), 101 deletions(-) diff --cc doc/protocol-spec.txt index 471f2c0,798da14..c11f653 --- a/doc/protocol-spec.txt +++ b/doc/protocol-spec.txt @@@ -16,13 -16,15 +16,15 @@@ The Twobfuscato 1. Primitives, notation, and constants. - H(x) is SHA256 of X + H(x) is SHA256 of x. + H^n(x) is H(x) called iteratively n times. + - E_K(s) is the AES-counter-mode encryption of s using the key K. + E_K(s) is the AES-CTR-128 encryption of s using K as key. - x | y is the concatenation of x and y - UINT32(n) is the 4 byte value of n in big-endian (network) order - SR(n) is n bytes of strong random data - WR(n) is n bytes of weaker random data + x | y is the concatenation of x and y. + UINT32(n) is the 4 byte value of n in big-endian (network) order. + SR(n) is n bytes of strong random data. + WR(n) is n bytes of weaker random data. "xyz" is the ASCII characters 'x', 'y', and 'z', not NUL-terminated. s[:n] is the first n bytes of s. s[n:] is the last n bytes of s.

1 0

[obfsproxy/master] Implemented iterated hashing and updated the protocol spec.
by nickm＠torproject.org 29 May '11

29 May '11

commit d63d9d56a0da3a51aa7ec599635ec8a02ab0c8cb Author: George Kadianakis <desnacked(a)gmail.com> Date: Wed May 25 02:13:37 2011 +0200 Implemented iterated hashing and updated the protocol spec. --- doc/protocol-spec.txt | 28 ++++++++++++++++++---------- src/protocols/obfs2.c | 21 ++++++++++++++++++++- src/protocols/obfs2.h | 1 + 3 files changed, 39 insertions(+), 11 deletions(-) diff --git a/doc/protocol-spec.txt b/doc/protocol-spec.txt index 9a7d4fa..0f9edf9 100644 --- a/doc/protocol-spec.txt +++ b/doc/protocol-spec.txt @@ -27,9 +27,10 @@ The Twobfuscator s[:n] is the first n bytes of s. s[n:] is the last n bytes of s. - MAGIC_VALUE is 0x2BF5CA7E - SEED_LENGTH is 16 - MAX_PADDING is 8192 + MAGIC_VALUE is 0x2BF5CA7E + SEED_LENGTH is 16 + MAX_PADDING is 8192 + HASH_ITERATIONS is 100000 KEYLEN is the length of the key used by E_K(s) -- that is, 16. IVLEN is the length of the IV used by E_K(s) -- that is, 16 @@ -38,6 +39,9 @@ The Twobfuscator MAC(s, x) = H(s | x | s) + Let n = HASH_ITERATIONS through section '2. Key establishment phase.'. + Then, H^n(x) is H(x) called iteratively n times. + A "byte" is an 8-bit octet. We require that HASHLEN >= KEYLEN + IVLEN @@ -49,12 +53,14 @@ The Twobfuscator a padding key as follows. The initiator generates: INIT_SEED = SR(SEED_LENGTH) - INIT_PAD_KEY = MAC("Initiator obfuscation padding", INIT_SEED)[:KEYLEN] + INIT_PAD_TEMP = MAC("Initiator obfuscation padding", INIT_SEED)[:KEYLEN] + INIT_PAD_KEY = H^n(INIT_PAD_TEMP) And the responder generates: RESP_SEED = SR(SEED_LENGTH) - RESP_PAD_KEY = MAC("Responder obfuscation padding", INIT_SEED)[:KEYLEN] + RESP_PAD_TEMP = MAC("Responder obfuscation padding", INIT_SEED)[:KEYLEN] + RESP_PAD_KEY = H^n(RESP_PAD_TEMP) Each then generates a random number PADLEN in range from 0 through MAX_PADDING (inclusive), and sends: @@ -73,10 +79,12 @@ The Twobfuscator INIT_SECRET = MAC("Initiator obfuscated data", INIT_SEED|RESP_SEED) RESP_SECRET = MAC("Responder obfuscated data", INIT_SEED|RESP_SEED) - INIT_KEY = INIT_SECRET[:KEYLEN] - INIT_IV = INIT_SECRET[KEYLEN:] - RESP_KEY = RESP_SECRET[:KEYLEN] - RESP_IV = RESP_SECRET[KEYLEN:] + INIT_MASTER_KEY = H^n(INIT_SECRET) + RESP_MASTER_KEY = H^n(RESP_SECRET) + INIT_KEY = INIT_MASTER_KEY[:KEYLEN] + INIT_IV = INIT_MASTER_KEY[KEYLEN:] + RESP_KEY = RESP_MASTER_KEY[:KEYLEN] + RESP_IV = RESP_MASTER_KEY[KEYLEN:] The INIT_KEY value keys a stream cipher used to encrypt values from initiator to responder thereafter. The stream cipher's IV is @@ -89,5 +97,5 @@ The Twobfuscator Optionally, if the client and server share a secret value SECRET, they can replace the MAC function with: - MAC(s,x) = MAC(s | x | SECRET | s) + MAC(s,x) = H(s | x | SECRET | s) diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index 3490d0e..6221bb2 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -72,10 +72,12 @@ static crypt_t * derive_key(void *s, const char *keytype) { obfs2_state_t *state = s; - crypt_t *cryptstate; uchar buf[SHA256_LENGTH]; digest_t *c = digest_new(); + digest_t *d; + int i; + digest_update(c, (uchar*)keytype, strlen(keytype)); if (seed_nonzero(state->initiator_seed)) digest_update(c, state->initiator_seed, OBFUSCATE_SEED_LENGTH); @@ -85,6 +87,13 @@ derive_key(void *s, const char *keytype) digest_update(c, state->secret_seed, SHARED_SECRET_LENGTH); digest_update(c, (uchar*)keytype, strlen(keytype)); digest_getdigest(c, buf, sizeof(buf)); + + for (i=0; i < OBFUSCATE_HASH_ITERATIONS; i++) { + d = digest_new(); + digest_update(d, buf, sizeof(buf)); + digest_getdigest(d, buf, sizeof(buf)); + } + cryptstate = crypt_new(buf, 16); crypt_set_iv(cryptstate, buf+16, 16); memset(buf, 0, sizeof(buf)); @@ -101,6 +110,9 @@ derive_padding_key(void *s, const uchar *seed, crypt_t *cryptstate; uchar buf[SHA256_LENGTH]; digest_t *c = digest_new(); + digest_t *d; + int i; + digest_update(c, (uchar*)keytype, strlen(keytype)); if (seed_nonzero(seed)) digest_update(c, seed, OBFUSCATE_SEED_LENGTH); @@ -108,6 +120,13 @@ derive_padding_key(void *s, const uchar *seed, digest_update(c, state->secret_seed, OBFUSCATE_SEED_LENGTH); digest_update(c, (uchar*)keytype, strlen(keytype)); digest_getdigest(c, buf, sizeof(buf)); + + for (i=0; i < OBFUSCATE_HASH_ITERATIONS; i++) { + d = digest_new(); + digest_update(d, buf, sizeof(buf)); + digest_getdigest(d, buf, sizeof(buf)); + } + cryptstate = crypt_new(buf, 16); crypt_set_iv(cryptstate, buf+16, 16); memset(buf, 0, 16); diff --git a/src/protocols/obfs2.h b/src/protocols/obfs2.h index 1f9f31d..0d70144 100644 --- a/src/protocols/obfs2.h +++ b/src/protocols/obfs2.h @@ -36,6 +36,7 @@ void *obfs2_new(struct protocol_t *proto_struct, #define OBFUSCATE_SEED_LENGTH 16 #define OBFUSCATE_MAX_PADDING 8192 #define OBFUSCATE_ZERO_SEED "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" +#define OBFUSCATE_HASH_ITERATIONS 100000 #define INITIATOR_PAD_TYPE "Initiator obfuscation padding" #define RESPONDER_PAD_TYPE "Responder obfuscation padding"

1 0

[obfsproxy/master] Stop doing iterative hashing when we don't have a shared secret.
by nickm＠torproject.org 29 May '11

29 May '11

commit 0da68ca3c40ffc775421ae732f70504ac74891fc Author: George Kadianakis <desnacked(a)gmail.com> Date: Thu May 26 00:33:46 2011 +0200 Stop doing iterative hashing when we don't have a shared secret. --- doc/protocol-spec.txt | 24 ++++++++++-------------- src/main.c | 3 ++- src/protocols/obfs2.c | 28 ++++++++++++++++------------ 3 files changed, 28 insertions(+), 27 deletions(-) diff --git a/doc/protocol-spec.txt b/doc/protocol-spec.txt index 0f9edf9..798da14 100644 --- a/doc/protocol-spec.txt +++ b/doc/protocol-spec.txt @@ -17,6 +17,8 @@ The Twobfuscator 1. Primitives, notation, and constants. H(x) is SHA256 of X + H^n(x) is H(x) called iteratively n times. + E_K(s) is the AES-counter-mode encryption of s using the key K. x | y is the concatenation of x and y @@ -39,9 +41,6 @@ The Twobfuscator MAC(s, x) = H(s | x | s) - Let n = HASH_ITERATIONS through section '2. Key establishment phase.'. - Then, H^n(x) is H(x) called iteratively n times. - A "byte" is an 8-bit octet. We require that HASHLEN >= KEYLEN + IVLEN @@ -53,14 +52,12 @@ The Twobfuscator a padding key as follows. The initiator generates: INIT_SEED = SR(SEED_LENGTH) - INIT_PAD_TEMP = MAC("Initiator obfuscation padding", INIT_SEED)[:KEYLEN] - INIT_PAD_KEY = H^n(INIT_PAD_TEMP) + INIT_PAD_KEY = MAC("Initiator obfuscation padding", INIT_SEED)[:KEYLEN] And the responder generates: RESP_SEED = SR(SEED_LENGTH) - RESP_PAD_TEMP = MAC("Responder obfuscation padding", INIT_SEED)[:KEYLEN] - RESP_PAD_KEY = H^n(RESP_PAD_TEMP) + RESP_PAD_KEY = MAC("Responder obfuscation padding", INIT_SEED)[:KEYLEN] Each then generates a random number PADLEN in range from 0 through MAX_PADDING (inclusive), and sends: @@ -79,12 +76,10 @@ The Twobfuscator INIT_SECRET = MAC("Initiator obfuscated data", INIT_SEED|RESP_SEED) RESP_SECRET = MAC("Responder obfuscated data", INIT_SEED|RESP_SEED) - INIT_MASTER_KEY = H^n(INIT_SECRET) - RESP_MASTER_KEY = H^n(RESP_SECRET) - INIT_KEY = INIT_MASTER_KEY[:KEYLEN] - INIT_IV = INIT_MASTER_KEY[KEYLEN:] - RESP_KEY = RESP_MASTER_KEY[:KEYLEN] - RESP_IV = RESP_MASTER_KEY[KEYLEN:] + INIT_KEY = INIT_SECRET[:KEYLEN] + INIT_IV = INIT_SECRET[KEYLEN:] + RESP_KEY = RESP_SECRET[:KEYLEN] + RESP_IV = RESP_SECRET[KEYLEN:] The INIT_KEY value keys a stream cipher used to encrypt values from initiator to responder thereafter. The stream cipher's IV is @@ -97,5 +92,6 @@ The Twobfuscator Optionally, if the client and server share a secret value SECRET, they can replace the MAC function with: - MAC(s,x) = H(s | x | SECRET | s) + MAC(s,x) = H^n(s | x | SECRET | s) + where n = HASH_ITERATIONS. diff --git a/src/main.c b/src/main.c index 59b6909..4c3c48c 100644 --- a/src/main.c +++ b/src/main.c @@ -128,7 +128,8 @@ main(int argc, const char **argv) mode, protocol, (struct sockaddr *)&ss_listen, sl_listen, sa_target, sl_target, - shared_secret, strlen(shared_secret)); + shared_secret, + shared_secret ? strlen(shared_secret) : 0); if (! listener) { printf("Couldn't create listener!\n"); return 4; diff --git a/src/protocols/obfs2.c b/src/protocols/obfs2.c index 4159691..b3fe590 100644 --- a/src/protocols/obfs2.c +++ b/src/protocols/obfs2.c @@ -75,8 +75,6 @@ derive_key(void *s, const char *keytype) crypt_t *cryptstate; uchar buf[SHA256_LENGTH]; digest_t *c = digest_new(); - digest_t *d; - int i; digest_update(c, (uchar*)keytype, strlen(keytype)); if (seed_nonzero(state->initiator_seed)) @@ -88,10 +86,14 @@ derive_key(void *s, const char *keytype) digest_update(c, (uchar*)keytype, strlen(keytype)); digest_getdigest(c, buf, sizeof(buf)); - for (i=0; i < OBFUSCATE_HASH_ITERATIONS; i++) { - d = digest_new(); - digest_update(d, buf, sizeof(buf)); - digest_getdigest(d, buf, sizeof(buf)); + if (seed_nonzero(state->secret_seed)) { + digest_t *d; + int i; + for (i=0; i < OBFUSCATE_HASH_ITERATIONS; i++) { + d = digest_new(); + digest_update(d, buf, sizeof(buf)); + digest_getdigest(d, buf, sizeof(buf)); + } } cryptstate = crypt_new(buf, 16); @@ -110,8 +112,6 @@ derive_padding_key(void *s, const uchar *seed, crypt_t *cryptstate; uchar buf[SHA256_LENGTH]; digest_t *c = digest_new(); - digest_t *d; - int i; digest_update(c, (uchar*)keytype, strlen(keytype)); if (seed_nonzero(seed)) @@ -121,10 +121,14 @@ derive_padding_key(void *s, const uchar *seed, digest_update(c, (uchar*)keytype, strlen(keytype)); digest_getdigest(c, buf, sizeof(buf)); - for (i=0; i < OBFUSCATE_HASH_ITERATIONS; i++) { - d = digest_new(); - digest_update(d, buf, sizeof(buf)); - digest_getdigest(d, buf, sizeof(buf)); + if (seed_nonzero(state->secret_seed)) { + digest_t *d; + int i; + for (i=0; i < OBFUSCATE_HASH_ITERATIONS; i++) { + d = digest_new(); + digest_update(d, buf, sizeof(buf)); + digest_getdigest(d, buf, sizeof(buf)); + } } cryptstate = crypt_new(buf, 16);

1 0

r24793: {} we'll want the style file too (projects/articles/crypto2011)
by Roger Dingledine 28 May '11

28 May '11

Author: arma Date: 2011-05-28 07:21:47 +0000 (Sat, 28 May 2011) New Revision: 24793 Added: projects/articles/crypto2011/llncs.cls Log: we'll want the style file too Added: projects/articles/crypto2011/llncs.cls =================================================================== --- projects/articles/crypto2011/llncs.cls (rev 0) +++ projects/articles/crypto2011/llncs.cls 2011-05-28 07:21:47 UTC (rev 24793) @@ -0,0 +1,1190 @@ +% LLNCS DOCUMENT CLASS -- version 2.14 (17-Aug-2004) +% Springer Verlag LaTeX2e support for Lecture Notes in Computer Science +% +%% +%% \CharacterTable +%% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z +%% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z +%% Digits \0\1\2\3\4\5\6\7\8\9 +%% Exclamation \! Double quote \" Hash (number) \# +%% Dollar \$ Percent \% Ampersand \& +%% Acute accent \' Left paren $ Right paren $ +%% Asterisk \* Plus \+ Comma \, +%% Minus \- Point \. Solidus \/ +%% Colon \: Semicolon \; Less than \< +%% Equals \= Greater than \> Question mark \? +%% Commercial at \@ Left bracket \[ Backslash \\ +%% Right bracket \] Circumflex \^ Underscore \_ +%% Grave accent \` Left brace \{ Vertical bar \| +%% Right brace \} Tilde \~} +%% +\NeedsTeXFormat{LaTeX2e}[1995/12/01] +\ProvidesClass{llncs}[2004/08/17 v2.14 +^^J LaTeX document class for Lecture Notes in Computer Science] +% Options +\let\if@envcntreset\iffalse +\DeclareOption{envcountreset}{\let\if@envcntreset\iftrue} +\DeclareOption{citeauthoryear}{\let\citeauthoryear=Y} +\DeclareOption{oribibl}{\let\oribibl=Y} +\let\if@custvec\iftrue +\DeclareOption{orivec}{\let\if@custvec\iffalse} +\let\if@envcntsame\iffalse +\DeclareOption{envcountsame}{\let\if@envcntsame\iftrue} +\let\if@envcntsect\iffalse +\DeclareOption{envcountsect}{\let\if@envcntsect\iftrue} +\let\if@runhead\iffalse +\DeclareOption{runningheads}{\let\if@runhead\iftrue} + +\let\if@openbib\iffalse +\DeclareOption{openbib}{\let\if@openbib\iftrue} + +% languages +\let\switcht@@therlang\relax +\def\ds@deutsch{\def\switcht@@therlang{\switcht@deutsch}} +\def\ds@francais{\def\switcht@@therlang{\switcht@francais}} + +\DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}} + +\ProcessOptions + +\LoadClass[twoside]{article} +\RequirePackage{multicol} % needed for the list of participants, index + +\setlength{\textwidth}{12.2cm} +\setlength{\textheight}{19.3cm} +\renewcommand\@pnumwidth{2em} +\renewcommand\(a)tocrmarg{3.5em} +% +\def\@dottedtocline#1#2#3#4#5{% + \ifnum #1>\c@tocdepth \else + \vskip \z@ \@plus.2\p@ + {\leftskip #2\relax \rightskip \@tocrmarg \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \parindent #2\relax\@afterindenttrue + \interlinepenalty\@M + \leavevmode + \@tempdima #3\relax + \advance\leftskip \@tempdima \null\nobreak\hskip -\leftskip + {#4}\nobreak + \leaders\hbox{$\m@th + \mkern \@dotsep mu\hbox{.}\mkern \@dotsep + mu$}\hfill + \nobreak + \hb@xt@\@pnumwidth{\hfil\normalfont \normalcolor #5}% + \par}% + \fi} +% +\def\switcht@albion{% +\def\abstractname{Abstract.} +\def\ackname{Acknowledgement.} +\def\andname{and} +\def\lastandname{\unskip, and} +\def\appendixname{Appendix} +\def\chaptername{Chapter} +\def\claimname{Claim} +\def\conjecturename{Conjecture} +\def\contentsname{Table of Contents} +\def\corollaryname{Corollary} +\def\definitionname{Definition} +\def\examplename{Example} +\def\exercisename{Exercise} +\def\figurename{Fig.} +\def\keywordname{{\bf Key words:}} +\def\indexname{Index} +\def\lemmaname{Lemma} +\def\contriblistname{List of Contributors} +\def\listfigurename{List of Figures} +\def\listtablename{List of Tables} +\def\mailname{{\it Correspondence to\/}:} +\def\noteaddname{Note added in proof} +\def\notename{Note} +\def\partname{Part} +\def\problemname{Problem} +\def\proofname{Proof} +\def\propertyname{Property} +\def\propositionname{Proposition} +\def\questionname{Question} +\def\remarkname{Remark} +\def\seename{see} +\def\solutionname{Solution} +\def\subclassname{{\it Subject Classifications\/}:} +\def\tablename{Table} +\def\theoremname{Theorem}} +\switcht@albion +% Names of theorem like environments are already defined +% but must be translated if another language is chosen +% +% French section +\def\switcht@francais{%\typeout{On parle francais.}% + \def\abstractname{R\'esum\'e.}% + \def\ackname{Remerciements.}% + \def\andname{et}% + \def\lastandname{ et}% + \def\appendixname{Appendice} + \def\chaptername{Chapitre}% + \def\claimname{Pr\'etention}% + \def\conjecturename{Hypoth\`ese}% + \def\contentsname{Table des mati\`eres}% + \def\corollaryname{Corollaire}% + \def\definitionname{D\'efinition}% + \def\examplename{Exemple}% + \def\exercisename{Exercice}% + \def\figurename{Fig.}% + \def\keywordname{{\bf Mots-cl\'e:}} + \def\indexname{Index} + \def\lemmaname{Lemme}% + \def\contriblistname{Liste des contributeurs} + \def\listfigurename{Liste des figures}% + \def\listtablename{Liste des tables}% + \def\mailname{{\it Correspondence to\/}:} + \def\noteaddname{Note ajout\'ee \`a l'\'epreuve}% + \def\notename{Remarque}% + \def\partname{Partie}% + \def\problemname{Probl\`eme}% + \def\proofname{Preuve}% + \def\propertyname{Caract\'eristique}% +%\def\propositionname{Proposition}% + \def\questionname{Question}% + \def\remarkname{Remarque}% + \def\seename{voir} + \def\solutionname{Solution}% + \def\subclassname{{\it Subject Classifications\/}:} + \def\tablename{Tableau}% + \def\theoremname{Th\'eor\`eme}% +} +% +% German section +\def\switcht@deutsch{%\typeout{Man spricht deutsch.}% + \def\abstractname{Zusammenfassung.}% + \def\ackname{Danksagung.}% + \def\andname{und}% + \def\lastandname{ und}% + \def\appendixname{Anhang}% + \def\chaptername{Kapitel}% + \def\claimname{Behauptung}% + \def\conjecturename{Hypothese}% + \def\contentsname{Inhaltsverzeichnis}% + \def\corollaryname{Korollar}% +%\def\definitionname{Definition}% + \def\examplename{Beispiel}% + \def\exercisename{\"Ubung}% + \def\figurename{Abb.}% + \def\keywordname{{\bf Schl\"usselw\"orter:}} + \def\indexname{Index} +%\def\lemmaname{Lemma}% + \def\contriblistname{Mitarbeiter} + \def\listfigurename{Abbildungsverzeichnis}% + \def\listtablename{Tabellenverzeichnis}% + \def\mailname{{\it Correspondence to\/}:} + \def\noteaddname{Nachtrag}% + \def\notename{Anmerkung}% + \def\partname{Teil}% +%\def\problemname{Problem}% + \def\proofname{Beweis}% + \def\propertyname{Eigenschaft}% +%\def\propositionname{Proposition}% + \def\questionname{Frage}% + \def\remarkname{Anmerkung}% + \def\seename{siehe} + \def\solutionname{L\"osung}% + \def\subclassname{{\it Subject Classifications\/}:} + \def\tablename{Tabelle}% +%\def\theoremname{Theorem}% +} + +% Ragged bottom for the actual page +\def\thisbottomragged{\def\@textbottom{\vskip\z@ plus.0001fil +\global\let\@textbottom\relax}} + +\renewcommand\small{% + \@setfontsize\small\@ixpt{11}% + \abovedisplayskip 8.5\p@ \@plus3\p@ \@minus4\p@ + \abovedisplayshortskip \z@ \@plus2\p@ + \belowdisplayshortskip 4\p@ \@plus2\p@ \@minus2\p@ + \def\@listi{\leftmargin\leftmargini + \parsep 0\p@ \@plus1\p@ \@minus\p@ + \topsep 8\p@ \@plus2\p@ \@minus4\p@ + \itemsep0\p@}% + \belowdisplayskip \abovedisplayskip +} + +\frenchspacing +\widowpenalty=10000 +\clubpenalty=10000 + +\setlength\oddsidemargin {63\p@} +\setlength\evensidemargin {63\p@} +\setlength\marginparwidth {90\p@} + +\setlength\headsep {16\p@} + +\setlength\footnotesep{7.7\p@} +\setlength\textfloatsep{8mm\@plus 2\p@ \@minus 4\p@} +\setlength\intextsep {8mm\@plus 2\p@ \@minus 2\p@} + +\setcounter{secnumdepth}{2} + +\newcounter {chapter} +\renewcommand\thechapter {\@arabic\c@chapter} + +\newif\if@mainmatter \@mainmattertrue +\newcommand\frontmatter{\cleardoublepage + \@mainmatterfalse\pagenumbering{Roman}} +\newcommand\mainmatter{\cleardoublepage + \@mainmattertrue\pagenumbering{arabic}} +\newcommand\backmatter{\if@openright\cleardoublepage\else\clearpage\fi + \@mainmatterfalse} + +\renewcommand\part{\cleardoublepage + \thispagestyle{empty}% + \if@twocolumn + \onecolumn + \@tempswatrue + \else + \@tempswafalse + \fi + \null\vfil + \secdef\@part\@spart} + +\def\@part[#1]#2{% + \ifnum \c@secnumdepth >-2\relax + \refstepcounter{part}% + \addcontentsline{toc}{part}{\thepart\hspace{1em}#1}% + \else + \addcontentsline{toc}{part}{#1}% + \fi + \markboth{}{}% + {\centering + \interlinepenalty \@M + \normalfont + \ifnum \c@secnumdepth >-2\relax + \huge\bfseries \partname~\thepart + \par + \vskip 20\p@ + \fi + \Huge \bfseries #2\par}% + \@endpart} +\def\@spart#1{% + {\centering + \interlinepenalty \@M + \normalfont + \Huge \bfseries #1\par}% + \@endpart} +\def\@endpart{\vfil\newpage + \if@twoside + \null + \thispagestyle{empty}% + \newpage + \fi + \if@tempswa + \twocolumn + \fi} + +\newcommand\chapter{\clearpage + \thispagestyle{empty}% + \global\@topnum\z@ + \@afterindentfalse + \secdef\@chapter\@schapter} +\def\@chapter[#1]#2{\ifnum \c@secnumdepth >\m@ne + \if@mainmatter + \refstepcounter{chapter}% + \typeout{\(a)chapapp\space\thechapter.}% + \addcontentsline{toc}{chapter}% + {\protect\numberline{\thechapter}#1}% + \else + \addcontentsline{toc}{chapter}{#1}% + \fi + \else + \addcontentsline{toc}{chapter}{#1}% + \fi + \chaptermark{#1}% + \addtocontents{lof}{\protect\addvspace{10\p@}}% + \addtocontents{lot}{\protect\addvspace{10\p@}}% + \if@twocolumn + \@topnewpage[\@makechapterhead{#2}]% + \else + \@makechapterhead{#2}% + \@afterheading + \fi} +\def\@makechapterhead#1{% +% \vspace*{50\p@}% + {\centering + \ifnum \c@secnumdepth >\m@ne + \if@mainmatter + \large\bfseries \@chapapp{} \thechapter + \par\nobreak + \vskip 20\p@ + \fi + \fi + \interlinepenalty\@M + \Large \bfseries #1\par\nobreak + \vskip 40\p@ + }} +\def\@schapter#1{\if@twocolumn + \@topnewpage[\@makeschapterhead{#1}]% + \else + \@makeschapterhead{#1}% + \@afterheading + \fi} +\def\@makeschapterhead#1{% +% \vspace*{50\p@}% + {\centering + \normalfont + \interlinepenalty\@M + \Large \bfseries #1\par\nobreak + \vskip 40\p@ + }} + +\renewcommand\section{\@startsection{section}{1}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {12\p@ \@plus 4\p@ \@minus 4\p@}% + {\normalfont\large\bfseries\boldmath + \rightskip=\z@ \@plus 8em\pretolerance=10000 }} +\renewcommand\subsection{\@startsection{subsection}{2}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {8\p@ \@plus 4\p@ \@minus 4\p@}% + {\normalfont\normalsize\bfseries\boldmath + \rightskip=\z@ \@plus 8em\pretolerance=10000 }} +\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}% + {-18\p@ \@plus -4\p@ \@minus -4\p@}% + {-0.5em \@plus -0.22em \@minus -0.1em}% + {\normalfont\normalsize\bfseries\boldmath}} +\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}% + {-12\p@ \@plus -4\p@ \@minus -4\p@}% + {-0.5em \@plus -0.22em \@minus -0.1em}% + {\normalfont\normalsize\itshape}} +\renewcommand\subparagraph[1]{\typeout{LLNCS warning: You should not use + \string\subparagraph\space with this class}\vskip0.5cm +You should not use \verb|\subparagraph| with this class.\vskip0.5cm} + +\DeclareMathSymbol{\Gamma}{\mathalpha}{letters}{"00} +\DeclareMathSymbol{\Delta}{\mathalpha}{letters}{"01} +\DeclareMathSymbol{\Theta}{\mathalpha}{letters}{"02} +\DeclareMathSymbol{\Lambda}{\mathalpha}{letters}{"03} +\DeclareMathSymbol{\Xi}{\mathalpha}{letters}{"04} +\DeclareMathSymbol{\Pi}{\mathalpha}{letters}{"05} +\DeclareMathSymbol{\Sigma}{\mathalpha}{letters}{"06} +\DeclareMathSymbol{\Upsilon}{\mathalpha}{letters}{"07} +\DeclareMathSymbol{\Phi}{\mathalpha}{letters}{"08} +\DeclareMathSymbol{\Psi}{\mathalpha}{letters}{"09} +\DeclareMathSymbol{\Omega}{\mathalpha}{letters}{"0A} + +\let\footnotesize\small + +\if@custvec +\def\vec#1{\mathchoice{\mbox{\boldmath$\displaystyle#1$}} +{\mbox{\boldmath$\textstyle#1$}} +{\mbox{\boldmath$\scriptstyle#1$}} +{\mbox{\boldmath$\scriptscriptstyle#1$}}} +\fi + +\def\squareforqed{\hbox{\rlap{$\sqcap$}$\sqcup$}} +\def\qed{\ifmmode\squareforqed\else{\unskip\nobreak\hfil +\penalty50\hskip1em\null\nobreak\hfil\squareforqed +\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi} + +\def\getsto{\mathrel{\mathchoice {\vcenter{\offinterlineskip +\halign{\hfil +$\displaystyle##$\hfil\cr\gets\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr\gets +\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr\gets +\cr\to\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +\gets\cr\to\cr}}}}} +\def\lid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil +$\displaystyle##$\hfil\cr<\cr\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr<\cr +\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr<\cr +\noalign{\vskip1pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +<\cr +\noalign{\vskip0.9pt}=\cr}}}}} +\def\gid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil +$\displaystyle##$\hfil\cr>\cr\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr>\cr +\noalign{\vskip1.2pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr>\cr +\noalign{\vskip1pt}=\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +>\cr +\noalign{\vskip0.9pt}=\cr}}}}} +\def\grole{\mathrel{\mathchoice {\vcenter{\offinterlineskip +\halign{\hfil +$\displaystyle##$\hfil\cr>\cr\noalign{\vskip-1pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr +>\cr\noalign{\vskip-1pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr +>\cr\noalign{\vskip-0.8pt}<\cr}}} +{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr +>\cr\noalign{\vskip-0.3pt}<\cr}}}}} +\def\bbbr{{\rm I\!R}} %reelle Zahlen +\def\bbbm{{\rm I\!M}} +\def\bbbn{{\rm I\!N}} %natuerliche Zahlen +\def\bbbf{{\rm I\!F}} +\def\bbbh{{\rm I\!H}} +\def\bbbk{{\rm I\!K}} +\def\bbbp{{\rm I\!P}} +\def\bbbone{{\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l} +{\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}} +\def\bbbc{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm C$}\hbox{\hbox +to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}}} +\def\bbbq{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm +Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise +0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}} +\def\bbbt{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm +T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm T$}\hbox{\hbox +to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}}} +\def\bbbs{{\mathchoice +{\setbox0=\hbox{$\displaystyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox +to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} +{\setbox0=\hbox{$\textstyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox +to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptstyle \rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox +to0pt{\kern0.5\wd0\vrule height0.45\ht0\hss}\box0}} +{\setbox0=\hbox{$\scriptscriptstyle\rm S$}\hbox{\raise0.5\ht0\hbox +to0pt{\kern0.4\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox +to0pt{\kern0.55\wd0\vrule height0.45\ht0\hss}\box0}}}} +\def\bbbz{{\mathchoice {\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}} +{\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}} +{\hbox{$\mathsf\scriptstyle Z\kern-0.3em Z$}} +{\hbox{$\mathsf\scriptscriptstyle Z\kern-0.2em Z$}}}} + +\let\ts\, + +\setlength\leftmargini {17\p@} +\setlength\leftmargin {\leftmargini} +\setlength\leftmarginii {\leftmargini} +\setlength\leftmarginiii {\leftmargini} +\setlength\leftmarginiv {\leftmargini} +\setlength \labelsep {.5em} +\setlength \labelwidth{\leftmargini} +\addtolength\labelwidth{-\labelsep} + +\def\@listI{\leftmargin\leftmargini + \parsep 0\p@ \@plus1\p@ \@minus\p@ + \topsep 8\p@ \@plus2\p@ \@minus4\p@ + \itemsep0\p@} +\let\@listi\@listI +\@listi +\def\@listii {\leftmargin\leftmarginii + \labelwidth\leftmarginii + \advance\labelwidth-\labelsep + \topsep 0\p@ \@plus2\p@ \@minus\p@} +\def\@listiii{\leftmargin\leftmarginiii + \labelwidth\leftmarginiii + \advance\labelwidth-\labelsep + \topsep 0\p@ \@plus\p@\@minus\p@ + \parsep \z@ + \partopsep \p@ \@plus\z@ \@minus\p@} + +\renewcommand\labelitemi{\normalfont\bfseries --} +\renewcommand\labelitemii{$\m@th\bullet$} + +\setlength\arraycolsep{1.4\p@} +\setlength\tabcolsep{1.4\p@} + +\def\tableofcontents{\chapter*{\contentsname\@mkboth{{\contentsname}}% + {{\contentsname}}} + \def\authcount##1{\setcounter{auco}{##1}\setcounter{@auth}{1}} + \def\lastand{\ifnum\value{auco}=2\relax + \unskip{} \andname\ + \else + \unskip \lastandname\ + \fi}% + \def\and{\stepcounter{@auth}\relax + \ifnum\value{@auth}=\value{auco}% + \lastand + \else + \unskip, + \fi}% + \@starttoc{toc}\if@restonecol\twocolumn\fi} + +\def\l@part#1#2{\addpenalty{\@secpenalty}% + \addvspace{2em plus\p@}% % space above part line + \begingroup + \parindent \z@ + \rightskip \z@ plus 5em + \hrule\vskip5pt + \large % same size as for a contribution heading + \bfseries\boldmath % set line in boldface + \leavevmode % TeX command to enter horizontal mode. + #1\par + \vskip5pt + \hrule + \vskip1pt + \nobreak % Never break after part entry + \endgroup} + +\def\@dotsep{2} + +\def\hyperhrefextend{\ifx\hyper@anchor\@undefined\else +{chapter.\thechapter}\fi} + +\def\addnumcontentsmark#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{\protect\numberline + {\thechapter}#3}{\thepage}\hyperhrefextend}} +\def\addcontentsmark#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{#3}{\thepage}\hyperhrefextend}} +\def\addcontentsmarkwop#1#2#3{% +\addtocontents{#1}{\protect\contentsline{#2}{#3}{0}\hyperhrefextend}} + +\def\@adcmk[#1]{\ifcase #1 \or +\def\@gtempa{\addnumcontentsmark}% + \or \def\@gtempa{\addcontentsmark}% + \or \def\@gtempa{\addcontentsmarkwop}% + \fi\@gtempa{toc}{chapter}} +\def\addtocmark{\@ifnextchar[{\@adcmk}{\@adcmk[3]}} + +\def\l@chapter#1#2{\addpenalty{-\@highpenalty} + \vskip 1.0em plus 1pt \@tempdima 1.5em \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima \hskip -\leftskip + {\large\bfseries\boldmath#1}\ifx0#2\hfil\null + \else + \nobreak + \leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern + \@dotsep mu$}\hfill + \nobreak\hbox to\@pnumwidth{\hss #2}% + \fi\par + \penalty\@highpenalty \endgroup} + +\def\l@title#1#2{\addpenalty{-\@highpenalty} + \addvspace{8pt plus 1pt} + \@tempdima \z@ + \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \parfillskip -\rightskip \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima \hskip -\leftskip + #1\nobreak + \leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern + \@dotsep mu$}\hfill + \nobreak\hbox to\@pnumwidth{\hss #2}\par + \penalty\@highpenalty \endgroup} + +\def\l@author#1#2{\addpenalty{\@highpenalty} + \@tempdima=15\p@ %\z@ + \begingroup + \parindent \z@ \rightskip \@tocrmarg + \advance\rightskip by 0pt plus 2cm + \pretolerance=10000 + \leavevmode \advance\leftskip\@tempdima %\hskip -\leftskip + \textit{#1}\par + \penalty\@highpenalty \endgroup} + +\setcounter{tocdepth}{0} +\newdimen\tocchpnum +\newdimen\tocsecnum +\newdimen\tocsectotal +\newdimen\tocsubsecnum +\newdimen\tocsubsectotal +\newdimen\tocsubsubsecnum +\newdimen\tocsubsubsectotal +\newdimen\tocparanum +\newdimen\tocparatotal +\newdimen\tocsubparanum +\tocchpnum=\z@ % no chapter numbers +\tocsecnum=15\p@ % section 88. plus 2.222pt +\tocsubsecnum=23\p@ % subsection 88.8 plus 2.222pt +\tocsubsubsecnum=27\p@ % subsubsection 88.8.8 plus 1.444pt +\tocparanum=35\p@ % paragraph 88.8.8.8 plus 1.666pt +\tocsubparanum=43\p@ % subparagraph 88.8.8.8.8 plus 1.888pt +\def\calctocindent{% +\tocsectotal=\tocchpnum +\advance\tocsectotal by\tocsecnum +\tocsubsectotal=\tocsectotal +\advance\tocsubsectotal by\tocsubsecnum +\tocsubsubsectotal=\tocsubsectotal +\advance\tocsubsubsectotal by\tocsubsubsecnum +\tocparatotal=\tocsubsubsectotal +\advance\tocparatotal by\tocparanum} +\calctocindent + +\def\l@section{\@dottedtocline{1}{\tocchpnum}{\tocsecnum}} +\def\l@subsection{\@dottedtocline{2}{\tocsectotal}{\tocsubsecnum}} +\def\l@subsubsection{\@dottedtocline{3}{\tocsubsectotal}{\tocsubsubsecnum}} +\def\l@paragraph{\@dottedtocline{4}{\tocsubsubsectotal}{\tocparanum}} +\def\l@subparagraph{\@dottedtocline{5}{\tocparatotal}{\tocsubparanum}} + +\def\listoffigures{\@restonecolfalse\if@twocolumn\@restonecoltrue\onecolumn + \fi\section*{\listfigurename\@mkboth{{\listfigurename}}{{\listfigurename}}} + \@starttoc{lof}\if@restonecol\twocolumn\fi} +\def\l@figure{\@dottedtocline{1}{0em}{1.5em}} + +\def\listoftables{\@restonecolfalse\if@twocolumn\@restonecoltrue\onecolumn + \fi\section*{\listtablename\@mkboth{{\listtablename}}{{\listtablename}}} + \@starttoc{lot}\if@restonecol\twocolumn\fi} +\let\l@table\l@figure + +\renewcommand\listoffigures{% + \section*{\listfigurename + \@mkboth{\listfigurename}{\listfigurename}}% + \@starttoc{lof}% + } + +\renewcommand\listoftables{% + \section*{\listtablename + \@mkboth{\listtablename}{\listtablename}}% + \@starttoc{lot}% + } + +\ifx\oribibl\undefined +\ifx\citeauthoryear\undefined +\renewenvironment{thebibliography}[1] + {\section*{\refname} + \def\(a)biblabel##1{##1.} + \small + \list{\@biblabel{\@arabic\c@enumiv}}% + {\settowidth\labelwidth{\@biblabel{#1}}% + \leftmargin\labelwidth + \advance\leftmargin\labelsep + \if@openbib + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \fi + \usecounter{enumiv}% + \let\p@enumiv\@empty + \renewcommand\theenumiv{\@arabic\c@enumiv}}% + \if@openbib + \renewcommand\newblock{\par}% + \else + \renewcommand\newblock{\hskip .11em \(a)plus.33em \(a)minus.07em}% + \fi + \sloppy\clubpenalty4000\widowpenalty4000% + \sfcode`\.=\@m} + {\def\@noitemerr + {\@latex@warning{Empty `thebibliography' environment}}% + \endlist} +\def\@lbibitem[#1]#2{\item[{[#1]}\hfill]\if@filesw + {\let\protect\noexpand\immediate + \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces} +\newcount\@tempcntc +\def\@citex[#1]#2{\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi + \@tempcnta\z@\@tempcntb\m@ne\def\@citea{}\@cite{\@for\@citeb:=#2\do + {\@ifundefined + {b@\@citeb}{\@citeo\@tempcntb\m@ne\@citea\def\@citea{,}{\bfseries + ?}\@warning + {Citation `\@citeb' on page \thepage \space undefined}}% + {\setbox\z@\hbox{\global\@tempcntc0\csname b@\@citeb\endcsname\relax}% + \ifnum\@tempcntc=\z@ \@citeo\@tempcntb\m@ne + \@citea\def\@citea{,}\hbox{\csname b@\@citeb\endcsname}% + \else + \advance\@tempcntb\@ne + \ifnum\@tempcntb=\@tempcntc + \else\advance\@tempcntb\m@ne\@citeo + \@tempcnta\@tempcntc\@tempcntb\@tempcntc\fi\fi}}\@citeo}{#1}} +\def\@citeo{\ifnum\@tempcnta>\@tempcntb\else + \@citea\def\@citea{,\,\hskip\z@skip}% + \ifnum\@tempcnta=\@tempcntb\the\@tempcnta\else + {\advance\@tempcnta\@ne\ifnum\@tempcnta=\@tempcntb \else + \def\@citea{--}\fi + \advance\@tempcnta\m@ne\the\@tempcnta\@citea\the\@tempcntb}\fi\fi} +\else +\renewenvironment{thebibliography}[1] + {\section*{\refname} + \small + \list{}% + {\settowidth\labelwidth{}% + \leftmargin\parindent + \itemindent=-\parindent + \labelsep=\z@ + \if@openbib + \advance\leftmargin\bibindent + \itemindent -\bibindent + \listparindent \itemindent + \parsep \z@ + \fi + \usecounter{enumiv}% + \let\p@enumiv\@empty + \renewcommand\theenumiv{}}% + \if@openbib + \renewcommand\newblock{\par}% + \else + \renewcommand\newblock{\hskip .11em \(a)plus.33em \(a)minus.07em}% + \fi + \sloppy\clubpenalty4000\widowpenalty4000% + \sfcode`\.=\@m} + {\def\@noitemerr + {\@latex@warning{Empty `thebibliography' environment}}% + \endlist} + \def\@cite#1{#1}% + \def\@lbibitem[#1]#2{\item[]\if@filesw + {\def\protect##1{\string ##1\space}\immediate + \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces} + \fi +\else +\@cons\@openbib@code{\noexpand\small} +\fi + +\def\idxquad{\hskip 10\p@}% space that divides entry from number + +\def\@idxitem{\par\hangindent 10\p@} + +\def\subitem{\par\setbox0=\hbox{--\enspace}% second order + \noindent\hangindent\wd0\box0}% index entry + +\def\subsubitem{\par\setbox0=\hbox{--\,--\enspace}% third + \noindent\hangindent\wd0\box0}% order index entry + +\def\indexspace{\par \vskip 10\p@ plus5\p@ minus3\p@\relax} + +\renewenvironment{theindex} + {\@mkboth{\indexname}{\indexname}% + \thispagestyle{empty}\parindent\z@ + \parskip\z@ \@plus .3\p@\relax + \let\item\par + \def\,{\relax\ifmmode\mskip\thinmuskip + \else\hskip0.2em\ignorespaces\fi}% + \normalfont\small + \begin{multicols}{2}[\@makeschapterhead{\indexname}]% + } + {\end{multicols}} + +\renewcommand\footnoterule{% + \kern-3\p@ + \hrule\@width 2truecm + \kern2.6\p@} + \newdimen\fnindent + \fnindent1em +\long\def\@makefntext#1{% + \parindent \fnindent% + \leftskip \fnindent% + \noindent + \llap{\hb@xt@1em{\hss\@makefnmark\ }}\ignorespaces#1} + +\long\def\@makecaption#1#2{% + \vskip\abovecaptionskip + \sbox\@tempboxa{{\bfseries #1.} #2}% + \ifdim \wd\@tempboxa >\hsize + {\bfseries #1.} #2\par + \else + \global \@minipagefalse + \hb@xt@\hsize{\hfil\box\@tempboxa\hfil}% + \fi + \vskip\belowcaptionskip} + +\def\fps@figure{htbp} +\def\fnum@figure{\figurename\thinspace\thefigure} +\def \@floatboxreset {% + \reset@font + \small + \@setnobreak + \@setminipage +} +\def\fps@table{htbp} +\def\fnum@table{\tablename~\thetable} +\renewenvironment{table} + {\setlength\abovecaptionskip{0\p@}% + \setlength\belowcaptionskip{10\p@}% + \@float{table}} + {\end@float} +\renewenvironment{table*} + {\setlength\abovecaptionskip{0\p@}% + \setlength\belowcaptionskip{10\p@}% + \@dblfloat{table}} + {\end@dblfloat} + +\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname + ext@#1\endcsname}{#1}{\protect\numberline{\csname + the#1\endcsname}{\ignorespaces #2}}\begingroup + \@parboxrestore + \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par + \endgroup} + +% LaTeX does not provide a command to enter the authors institute +% addresses. The \institute command is defined here. + +\newcounter{@inst} +\newcounter{@auth} +\newcounter{auco} +\newdimen\instindent +\newbox\authrun +\newtoks\authorrunning +\newtoks\tocauthor +\newbox\titrun +\newtoks\titlerunning +\newtoks\toctitle + +\def\clearheadinfo{\gdef\@author{No Author Given}% + \gdef\@title{No Title Given}% + \gdef\@subtitle{}% + \gdef\@institute{No Institute Given}% + \gdef\@thanks{}% + \global\titlerunning={}\global\authorrunning={}% + \global\toctitle={}\global\tocauthor={}} + +\def\institute#1{\gdef\@institute{#1}} + +\def\institutename{\par + \begingroup + \parskip=\z@ + \parindent=\z@ + \setcounter{@inst}{1}% + \def\and{\par\stepcounter{@inst}% + \noindent$^{\the@inst}$\enspace\ignorespaces}% + \setbox0=\vbox{\def\thanks##1{}\@institute}% + \ifnum\c@@inst=1\relax + \gdef\fnnstart{0}% + \else + \xdef\fnnstart{\c@@inst}% + \setcounter{@inst}{1}% + \noindent$^{\the@inst}$\enspace + \fi + \ignorespaces + \@institute\par + \endgroup} + +\def\@fnsymbol#1{\ensuremath{\ifcase#1\or\star\or{\star\star}\or + {\star\star\star}\or \dagger\or \ddagger\or + \mathchar "278\or \mathchar "27B\or \|\or **\or \dagger\dagger + \or \ddagger\ddagger \else\@ctrerr\fi}} + +\def\inst#1{\unskip$^{#1}$} +\def\fnmsep{\unskip$^,$} +\def\email#1{{\tt#1}} +\AtBeginDocument{\@ifundefined{url}{\def\url#1{#1}}{}% +\@ifpackageloaded{babel}{% +\@ifundefined{extrasenglish}{}{\addto\extrasenglish{\switcht@albion}}% +\@ifundefined{extrasfrenchb}{}{\addto\extrasfrenchb{\switcht@francais}}% +\@ifundefined{extrasgerman}{}{\addto\extrasgerman{\switcht@deutsch}}% +}{\switcht@@therlang}% +} +\def\homedir{\~{ }} + +\def\subtitle#1{\gdef\@subtitle{#1}} +\clearheadinfo +% +\renewcommand\maketitle{\newpage + \refstepcounter{chapter}% + \stepcounter{section}% + \setcounter{section}{0}% + \setcounter{subsection}{0}% + \setcounter{figure}{0} + \setcounter{table}{0} + \setcounter{equation}{0} + \setcounter{footnote}{0}% + \begingroup + \parindent=\z@ + \renewcommand\thefootnote{\@fnsymbol\c@footnote}% + \if@twocolumn + \ifnum \col@number=\@ne + \@maketitle + \else + \twocolumn[\@maketitle]% + \fi + \else + \newpage + \global\@topnum\z@ % Prevents figures from going at top of page. + \@maketitle + \fi + \thispagestyle{empty}\@thanks +% + \def\\{\unskip\ \ignorespaces}\def\inst##1{\unskip{}}% + \def\thanks##1{\unskip{}}\def\fnmsep{\unskip}% + \instindent=\hsize + \advance\instindent by-\headlineindent + \if!\the\toctitle!\addcontentsline{toc}{title}{\@title}\else + \addcontentsline{toc}{title}{\the\toctitle}\fi + \if@runhead + \if!\the\titlerunning!\else + \edef\@title{\the\titlerunning}% + \fi + \global\setbox\titrun=\hbox{\small\rm\unboldmath\ignorespaces\@title}% + \ifdim\wd\titrun>\instindent + \typeout{Title too long for running head. Please supply}% + \typeout{a shorter form with \string\titlerunning\space prior to + \string\maketitle}% + \global\setbox\titrun=\hbox{\small\rm + Title Suppressed Due to Excessive Length}% + \fi + \xdef\@title{\copy\titrun}% + \fi +% + \if!\the\tocauthor!\relax + {\def\and{\noexpand\protect\noexpand\and}% + \protected@xdef\toc@uthor{\@author}}% + \else + \def\\{\noexpand\protect\noexpand\newline}% + \protected@xdef\scratch{\the\tocauthor}% + \protected@xdef\toc@uthor{\scratch}% + \fi + \addtocontents{toc}{\noexpand\protect\noexpand\authcount{\the\c@auco}}% + \addcontentsline{toc}{author}{\toc@uthor}% + \if@runhead + \if!\the\authorrunning! + \value{@inst}=\value{@auth}% + \setcounter{@auth}{1}% + \else + \edef\@author{\the\authorrunning}% + \fi + \global\setbox\authrun=\hbox{\small\unboldmath\@author\unskip}% + \ifdim\wd\authrun>\instindent + \typeout{Names of authors too long for running head. Please supply}% + \typeout{a shorter form with \string\authorrunning\space prior to + \string\maketitle}% + \global\setbox\authrun=\hbox{\small\rm + Authors Suppressed Due to Excessive Length}% + \fi + \xdef\@author{\copy\authrun}% + \markboth{\@author}{\@title}% + \fi + \endgroup + \setcounter{footnote}{\fnnstart}% + \clearheadinfo} +% +\def\@maketitle{\newpage + \markboth{}{}% + \def\lastand{\ifnum\value{@inst}=2\relax + \unskip{} \andname\ + \else + \unskip \lastandname\ + \fi}% + \def\and{\stepcounter{@auth}\relax + \ifnum\value{@auth}=\value{@inst}% + \lastand + \else + \unskip, + \fi}% + \begin{center}% + \let\newline\\ + {\Large \bfseries\boldmath + \pretolerance=10000 + \@title \par}\vskip .8cm +\if!\@subtitle!\else {\large \bfseries\boldmath + \vskip -.65cm + \pretolerance=10000 + \@subtitle \par}\vskip .8cm\fi + \setbox0=\vbox{\setcounter{@auth}{1}\def\and{\stepcounter{@auth}}% + \def\thanks##1{}\@author}% + \global\value{@inst}=\value{@auth}% + \global\value{auco}=\value{@auth}% + \setcounter{@auth}{1}% +{\lineskip .5em +\noindent\ignorespaces +\(a)author\vskip.35cm} + {\small\institutename} + \end{center}% + } + +% definition of the "\spnewtheorem" command. +% +% Usage: +% +% \spnewtheorem{env_nam}{caption}[within]{cap_font}{body_font} +% or \spnewtheorem{env_nam}[numbered_like]{caption}{cap_font}{body_font} +% or \spnewtheorem*{env_nam}{caption}{cap_font}{body_font} +% +% New is "cap_font" and "body_font". It stands for +% fontdefinition of the caption and the text itself. +% +% "\spnewtheorem*" gives a theorem without number. +% +% A defined spnewthoerem environment is used as described +% by Lamport. +% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\def\@thmcountersep{} +\def\(a)thmcounterend{.} + +\def\spnewtheorem{\@ifstar{\@sthm}{\@Sthm}} + +% definition of \spnewtheorem with number + +\def\@spnthm#1#2{% + \@ifnextchar[{\@spxnthm{#1}{#2}}{\@spynthm{#1}{#2}}} +\def\@Sthm#1{\@ifnextchar[{\@spothm{#1}}{\@spnthm{#1}}} + +\def\@spxnthm#1#2[#3]#4#5{\expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}\@addtoreset{#1}{#3}% + \expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand + \csname the#3\endcsname \noexpand\@thmcountersep \@thmcounter{#1}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@spynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}% + \expandafter\xdef\csname the#1\endcsname{\@thmcounter{#1}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#3}{#4}}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@spothm#1[#2]#3#4#5{% + \@ifundefined{c@#2}{\@latexerr{No theorem environment `#2' defined}\@eha}% + {\expandafter\@ifdefinable\csname #1\endcsname + {\global\@namedef{the#1}{\@nameuse{the#2}}% + \expandafter\xdef\csname #1name\endcsname{#3}% + \global\@namedef{#1}{\@spthm{#2}{\csname #1name\endcsname}{#4}{#5}}% + \global\@namedef{end#1}{\@endtheorem}}}} + +\def\@spthm#1#2#3#4{\topsep 7\p@ \@plus2\p@ \@minus4\p@ +\refstepcounter{#1}% +\@ifnextchar[{\@spythm{#1}{#2}{#3}{#4}}{\@spxthm{#1}{#2}{#3}{#4}}} + +\def\@spxthm#1#2#3#4{\@spbegintheorem{#2}{\csname the#1\endcsname}{#3}{#4}% + \ignorespaces} + +\def\@spythm#1#2#3#4[#5]{\@spopargbegintheorem{#2}{\csname + the#1\endcsname}{#5}{#3}{#4}\ignorespaces} + +\def\@spbegintheorem#1#2#3#4{\trivlist + \item[\hskip\labelsep{#3#1\ #2\@thmcounterend}]#4} + +\def\@spopargbegintheorem#1#2#3#4#5{\trivlist + \item[\hskip\labelsep{#4#1\ #2}]{#4(#3)\@thmcounterend\ }#5} + +% definition of \spnewtheorem* without number + +\def\@sthm#1#2{\@Ynthm{#1}{#2}} + +\def\@Ynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname + {\global\@namedef{#1}{\@Thm{\csname #1name\endcsname}{#3}{#4}}% + \expandafter\xdef\csname #1name\endcsname{#2}% + \global\@namedef{end#1}{\@endtheorem}}} + +\def\@Thm#1#2#3{\topsep 7\p@ \@plus2\p@ \@minus4\p@ +\@ifnextchar[{\@Ythm{#1}{#2}{#3}}{\@Xthm{#1}{#2}{#3}}} + +\def\@Xthm#1#2#3{\@Begintheorem{#1}{#2}{#3}\ignorespaces} + +\def\@Ythm#1#2#3[#4]{\@Opargbegintheorem{#1} + {#4}{#2}{#3}\ignorespaces} + +\def\@Begintheorem#1#2#3{#3\trivlist + \item[\hskip\labelsep{#2#1\@thmcounterend}]} + +\def\@Opargbegintheorem#1#2#3#4{#4\trivlist + \item[\hskip\labelsep{#3#1}]{#3(#2)\@thmcounterend\ }} + +\if@envcntsect + \def\(a)thmcountersep{.} + \spnewtheorem{theorem}{Theorem}[section]{\bfseries}{\itshape} +\else + \spnewtheorem{theorem}{Theorem}{\bfseries}{\itshape} + \if@envcntreset + \@addtoreset{theorem}{section} + \else + \@addtoreset{theorem}{chapter} + \fi +\fi + +%definition of divers theorem environments +\spnewtheorem*{claim}{Claim}{\itshape}{\rmfamily} +\spnewtheorem*{proof}{Proof}{\itshape}{\rmfamily} +\if@envcntsame % alle Umgebungen wie Theorem. + \def\spn@wtheorem#1#2#3#4{\@spothm{#1}[theorem]{#2}{#3}{#4}} +\else % alle Umgebungen mit eigenem Zaehler + \if@envcntsect % mit section numeriert + \def\spn@wtheorem#1#2#3#4{\@spxnthm{#1}{#2}[section]{#3}{#4}} + \else % nicht mit section numeriert + \if@envcntreset + \def\spn@wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4} + \@addtoreset{#1}{section}} + \else + \def\spn@wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4} + \@addtoreset{#1}{chapter}}% + \fi + \fi +\fi +\spn@wtheorem{case}{Case}{\itshape}{\rmfamily} +\spn@wtheorem{conjecture}{Conjecture}{\itshape}{\rmfamily} +\spn@wtheorem{corollary}{Corollary}{\bfseries}{\itshape} +\spn@wtheorem{definition}{Definition}{\bfseries}{\itshape} +\spn@wtheorem{example}{Example}{\itshape}{\rmfamily} +\spn@wtheorem{exercise}{Exercise}{\itshape}{\rmfamily} +\spn@wtheorem{lemma}{Lemma}{\bfseries}{\itshape} +\spn@wtheorem{note}{Note}{\itshape}{\rmfamily} +\spn@wtheorem{problem}{Problem}{\itshape}{\rmfamily} +\spn@wtheorem{property}{Property}{\itshape}{\rmfamily} +\spn@wtheorem{proposition}{Proposition}{\bfseries}{\itshape} +\spn@wtheorem{question}{Question}{\itshape}{\rmfamily} +\spn@wtheorem{solution}{Solution}{\itshape}{\rmfamily} +\spn@wtheorem{remark}{Remark}{\itshape}{\rmfamily} + +\def\@takefromreset#1#2{% + \def\@tempa{#1}% + \let\@tempd\@elt + \def\@elt##1{% + \def\@tempb{##1}% + \ifx\@tempa\@tempb\else + \@addtoreset{##1}{#2}% + \fi}% + \expandafter\expandafter\let\expandafter\@tempc\csname cl@#2\endcsname + \expandafter\def\csname cl@#2\endcsname{}% + \@tempc + \let\@elt\@tempd} + +\def\theopargself{\def\@spopargbegintheorem##1##2##3##4##5{\trivlist + \item[\hskip\labelsep{##4##1\ ##2}]{##4##3\@thmcounterend\ }##5} + \def\@Opargbegintheorem##1##2##3##4{##4\trivlist + \item[\hskip\labelsep{##3##1}]{##3##2\@thmcounterend\ }} + } + +\renewenvironment{abstract}{% + \list{}{\advance\topsep by0.35cm\relax\small + \leftmargin=1cm + \labelwidth=\z@ + \listparindent=\z@ + \itemindent\listparindent + \rightmargin\leftmargin}\item[\hskip\labelsep + \bfseries\abstractname]} + {\endlist} + +\newdimen\headlineindent % dimension for space between +\headlineindent=1.166cm % number and text of headings. + +\def\ps@headings{\let\@mkboth\@gobbletwo + \let\@oddfoot\@empty\let\@evenfoot\@empty + \def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}% + \leftmark\hfil} + \def\@oddhead{\normalfont\small\hfil\rightmark\hspace{\headlineindent}% + \llap{\thepage}} + \def\chaptermark##1{}% + \def\sectionmark##1{}% + \def\subsectionmark##1{}} + +\def\ps@titlepage{\let\@mkboth\@gobbletwo + \let\@oddfoot\@empty\let\@evenfoot\@empty + \def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}% + \hfil} + \def\@oddhead{\normalfont\small\hfil\hspace{\headlineindent}% + \llap{\thepage}} + \def\chaptermark##1{}% + \def\sectionmark##1{}% + \def\subsectionmark##1{}} + +\if@runhead\ps@headings\else +\ps@empty\fi + +\setlength\arraycolsep{1.4\p@} +\setlength\tabcolsep{1.4\p@} + +\endinput +%end of file llncs.cls Property changes on: projects/articles/crypto2011/llncs.cls ___________________________________________________________________ Added: svn:executable + *

1 0

r24792: {} and a pdf to go with it (projects/articles/crypto2011)
by Roger Dingledine 28 May '11

28 May '11

Author: arma Date: 2011-05-28 07:19:03 +0000 (Sat, 28 May 2011) New Revision: 24792 Added: projects/articles/crypto2011/crypto2011-tor.pdf Log: and a pdf to go with it Added: projects/articles/crypto2011/crypto2011-tor.pdf =================================================================== (Binary files differ) Property changes on: projects/articles/crypto2011/crypto2011-tor.pdf ___________________________________________________________________ Added: svn:mime-type + application/octet-stream

1 0

r24791: {} my abstract for the crypto 2011 talk (in projects/articles: . crypto2011)
by Roger Dingledine 28 May '11

28 May '11

Author: arma Date: 2011-05-28 07:16:03 +0000 (Sat, 28 May 2011) New Revision: 24791 Added: projects/articles/crypto2011/ projects/articles/crypto2011/crypto2011-tor.bib projects/articles/crypto2011/crypto2011-tor.tex projects/articles/crypto2011/direct-users-2011-04-01-300-eg-2010-12-01.png projects/articles/crypto2011/direct-users-2011-04-01-300-ir-2010-12-01.png projects/articles/crypto2011/direct-users-2011-04-01-300-ly-2010-12-01.png projects/articles/crypto2011/direct-users-2011-04-01-300-sa-2010-09-01.png projects/articles/crypto2011/direct-users-2011-04-01-300-tn-2010-12-01.png Log: my abstract for the crypto 2011 talk Added: projects/articles/crypto2011/crypto2011-tor.bib =================================================================== --- projects/articles/crypto2011/crypto2011-tor.bib (rev 0) +++ projects/articles/crypto2011/crypto2011-tor.bib 2011-05-28 07:16:03 UTC (rev 24791) @@ -0,0 +1,154 @@ +@inproceedings{dingledine2004tor, + author = {Roger Dingledine and Nick Mathewson and Paul Syverson}, + title = {Tor: The Second-Generation Onion Router}, + booktitle = {Proceedings of the 13th USENIX Security Symposium}, + year = {2004}, + month = {August}, + pages = {303--320}, +} + +@inproceedings{mccoy2008shining, + title = {Shining Light in Dark Places: Understanding the {Tor} Network}, + author = {Damon McCoy and Kevin Bauer and Dirk Grunwald and Tadayoshi + Kohno and Douglas Sicker}, + booktitle = {Proceedings of the Eighth Symposium on Privacy Enhancing + Technologies (PETS 2008)}, + year = {2008}, + month = {July}, + address = {Leuven, Belgium}, + pages = {63--76}, + editor = {Nikita Borisov and Ian Goldberg}, + publisher = {Springer}, + series = {Lecture Notes in Computer Science}, + volume = {5134}, +} + +@inproceedings{differential, + title = {Differential Privacy}, + author = {Cynthia Dwork}, + booktitle = {33rd International Colloquium on Automata, Languages +and Programming (ICALP)}, + year = {2006}, + month = {July}, + address = {Venice, Italy}, + pages = {1--12}, + publisher = {Springer}, + series = {Lecture Notes in Computer Science}, + volume = {4052}, +} + +@techreport{loesing2009measuring, + title = {Measuring the {Tor} Network from Public Directory Information}, + author = {Karsten Loesing}, + institution = {2nd Hot Topics in Privacy Enhancing Technologies (HotPETs + 2009)}, + year = {2009}, + month = {August}, + address = {Seattle, WA, USA}, +} + +@inproceedings{loesing2008performance, + author = {Karsten Loesing and Werner Sandmann and Christian Wilms and Guido Wirtz}, + title = {Performance Measurements and Statistics of {Tor} Hidden Services}, + booktitle = {Proceedings of the International Symposium on Applications and the Internet (SAINT 2008)}, + month = {July}, + year = {2008}, + address = {Turku, Finland}, + publisher = {IEEE Computer Society} +} + +@inproceedings{lenhard2009performance, + title = {Performance Measurements of {Tor} Hidden Services in Low-Bandwidth Access Networks}, + author = {J{\"o}rg Lenhard and Karsten Loesing and Guido Wirtz}, + booktitle = {Proceedings of the 7th International Conference on + Applied Cryptography and Network Security (ACNS 09), Paris-Rocquencourt, France}, + month = {June}, + year = {2009}, +} + +@inproceedings{wendolsky2007performance, + title = {Performance Comparison of Low-Latency Anonymisation Services from a User Perspective}, + author = {Rolf Wendolsky and Dominik Herrmann and Hannes Federrath}, + booktitle = {Proceedings of the Seventh Symposium on Privacy Enhancing Technologies (PET 2007)}, + pages = {233--253}, + year = {2007}, + month = {June}, + series = {Lecture Notes in Computer Science}, + publisher = {Springer}, + editor = {Nikita Borisov and Philippe Golle}, + volume = {4776}, +} + +@manual{tor2009dirspec, + author = {The Tor Project}, + title = {Tor directory protocol, version 3}, + year = {2009}, + note = {\url{https://git.torproject.org/checkout/tor/master/doc/spec/dir-spec.txt}}, +} + +@manual{bridges-spec, + author = {The Tor Project}, + title = {Tor bridges specification}, + year = {2009}, + note = {\url{https://git.torproject.org/checkout/tor/master/doc/spec/bridges-spec.txt}}, +} + +@inproceedings{murdoch-pet2007, + title = {Sampled Traffic Analysis by {I}nternet-Exchange-Level Adversaries}, + author = {Steven J. Murdoch and Piotr Zieli{\'n}ski}, + booktitle = {Proceedings of the Seventh Workshop on Privacy Enhancing Technologies (PET 2007)}, + year = {2007}, + month = {June}, + address = {Ottawa, Canada}, + editor = {Nikita Borisov and Philippe Golle}, + publisher = {Springer}, + series = {LNCS 4776}, +} + +@inproceedings{hs-attack06, + title = {Locating Hidden Servers}, + author = {Lasse {\O}verlier and Paul Syverson}, + booktitle = {Proceedings of the 2006 IEEE Symposium on Security and Privacy}, + year = {2006}, + month = {May}, + publisher = {IEEE CS}, + www_pdf_url = {http://www.onion-router.net/Publications/locating-hidden-servers.pdf}, + www_section = {Traffic analysis}, +} + +@misc{colorado-irb-response, + author = {Damon McCoy and Kevin Bauer and Dirk Grunwald and Tadayoshi Kohno and Douglas Sicker}, + title = {Response to Tor Study}, + note = {\url{http://systems.cs.colorado.edu/mediawiki/index.php/Response_To_Tor_Study}}, +} + +@misc{tor-legal-faq, + key = "Tor-legal-faq", + author = "{Electronic Frontier Foundation}", + title = "Tor: Legal {FAQ} for {T}or Server Operators", + howpublished = {\url{https://www.torproject.org/eff/tor-legal-faq.html}} +} + +@inproceedings{wecsr10measuring-tor, + title = {A Case Study on Measuring Statistical Data in the {T}or Anonymity Network}, + author = {Karsten Loesing and Steven J. Murdoch and Roger Dingledine}, + booktitle = {Proceedings of the Workshop on Ethics in Computer Security Research (WECSR 2010)}, + year = {2010}, + month = {January}, + address = {Tenerife, Canary Islands, Spain}, + publisher = {Springer}, + series = {LNCS 6054}, + editor = {Sven Dietrich}, + howpublished = {\url{https://metrics.torproject.org/papers/wecsr10.pdf}}, +} + +@techreport{tor-blocking, + title = {Design of a blocking-resistant anonymity system}, + author = {Roger Dingledine and Nick Mathewson}, + institution = {The Tor Project}, + number = {2006-1}, + year = {2006}, + month = {November}, + howpublished = {\url{https://svn.torproject.org/svn/projects/design-paper/blocking.pdf}}, +} + Property changes on: projects/articles/crypto2011/crypto2011-tor.bib ___________________________________________________________________ Added: svn:executable + * Added: projects/articles/crypto2011/crypto2011-tor.tex =================================================================== --- projects/articles/crypto2011/crypto2011-tor.tex (rev 0) +++ projects/articles/crypto2011/crypto2011-tor.tex 2011-05-28 07:16:03 UTC (rev 24791) @@ -0,0 +1,113 @@ +\documentclass{llncs} +\usepackage[cmex10]{amsmath} +\usepackage{subfigure} +\usepackage[pdftex]{graphicx} +\usepackage{graphics} +\usepackage{color} +\pagestyle{empty} + +%\usepackage[pdftex,% +% breaklinks=true,% +% colorlinks=true,% +% linkcolor=black,% +% citecolor=black,% +% urlcolor=black,% +% bookmarks=false,% +% pdfpagemode=UseNone,% +%]{hyperref} + +\begin{document} +\title{Tor and circumvention: lessons learned\\ +(Abstract to go with invited talk)} +\author{Roger Dingledine} +\institute{The Tor Project} +\maketitle + +Tor is a free-software anonymizing overlay network that helps people +around the world use the Internet in safety. Tor's 2500 volunteer relays +carry almost 10Gb/s of traffic for several hundred thousand users each day. + +While many in the +research community know Tor as the primary fielded system in the anonymous +communications literature~\cite{dingledine2004tor}, Tor has also played a +central role in recent +research on \emph{blocking resistance}. That is, even if an anonymity +system provides +great anonymity, a government censor can render it moot by simply +blocking the relays. In recent years we streamlined Tor's +network communications to look more like ordinary SSL, and we introduced +``bridge relays'' that are harder for an attacker to find and block than +Tor's public relays~\cite{tor-blocking}. + +Tor played a key role in several Middle Eastern countries in early +2011. In this talk I'll walk the audience through how Iran used +its Nokia DPI boxes to filter SSL flows that used Tor's original Diffie-Hellman +parameter $p$; the surge in Tor traffic when Egypt blocked Facebook and +the flatline when they unplugged the net; the continued bad news for +Libya's Internet; and an intriguing trend in Saudi Arabia. I'll also +cover current trends in China and Tunisia (not pictured). + +\begin{figure}[h] +\begin{minipage}{0.495\textwidth} +\includegraphics[width=\linewidth]{direct-users-2011-04-01-300-ir-2010-12-01.png} +\end{minipage} +\begin{minipage}{0.495\textwidth} +\includegraphics[width=\linewidth]{direct-users-2011-04-01-300-eg-2010-12-01.png} +\end{minipage} +\begin{minipage}{0.495\textwidth} +\includegraphics[width=\linewidth]{direct-users-2011-04-01-300-ly-2010-12-01.png} +\end{minipage} +\begin{minipage}{0.495\textwidth} +\includegraphics[width=\linewidth]{direct-users-2011-04-01-300-sa-2010-09-01.png} +\end{minipage} +\caption{Estimates of daily Tor clients connecting from each country} +\end{figure} + +The data for these user graphs, along with historical Tor network +data and ongoing performance statistics, are all available at +https://metrics.torproject.org/. Our WECSR'10 +paper~\cite{wecsr10measuring-tor} explains our +aggregation techniques and why we think they're safe---we'd love for you +to show us that we're wrong. Further, if you're working on Tor-related +research, please talk to us (https://torproject.org/research) +so we can explain what's available and help interpret your results. + +\subsection*{Some open questions from the anonymity field} + +Here are a few examples of open anonymity and blocking-resistance +problems: + +1) How effective is the traffic correlation attack really? Tor's threat +model assumes that an adversary who can see a traffic flow into the Tor +network and the corresponding flow out of the Tor network can correlate +them with high probability and low false positives. Recent results from +Steven Murdoch~\cite{murdoch-pet2007} show confirmation attacks even when both +sides only see a small sample of traffic on each side. But how quick +can the attack actually be in practice, using how little traffic? Are +there effective padding schemes to make correlation less effective? + +2) For various diversity metrics (like entropy), how has the diversity +of the Tor network changed over time? How robust is it to change or +attack?{\footnote{https://blog.torproject.org/blog/research-problem-measuring-safety-tor-network}} + +3) How can we automatically recognize blocking events---when Tor relays +are censored at a firewall by destination address or by traffic flow +characteristics? + +4) Clients who are censored from the public Tor relays can use private +addresses to ``bridge'' into the public Tor network. What strategies +should we use to give out these addresses such that legitimate users +get enough addresses but adversaries can't learn too many? + +5) How can we make it hard for censors to recognize Tor traffic flows by +content (e.g.\ distinguishing Tor's handshake from other expected protocols) +and by traffic characteristics (packet size, volume, and timing)? We need +\emph{obfuscation} metrics to let us anticipate which protocols will +blend in better with background traffic or otherwise defeat deep packet +inspection (DPI) algorithms. + +\bibliographystyle{plain} \bibliography{crypto2011-tor} +\end{document} + +\end{document} + Added: projects/articles/crypto2011/direct-users-2011-04-01-300-eg-2010-12-01.png =================================================================== (Binary files differ) Property changes on: projects/articles/crypto2011/direct-users-2011-04-01-300-eg-2010-12-01.png ___________________________________________________________________ Added: svn:mime-type + application/octet-stream Added: projects/articles/crypto2011/direct-users-2011-04-01-300-ir-2010-12-01.png =================================================================== (Binary files differ) Property changes on: projects/articles/crypto2011/direct-users-2011-04-01-300-ir-2010-12-01.png ___________________________________________________________________ Added: svn:mime-type + application/octet-stream Added: projects/articles/crypto2011/direct-users-2011-04-01-300-ly-2010-12-01.png =================================================================== (Binary files differ) Property changes on: projects/articles/crypto2011/direct-users-2011-04-01-300-ly-2010-12-01.png ___________________________________________________________________ Added: svn:mime-type + application/octet-stream Added: projects/articles/crypto2011/direct-users-2011-04-01-300-sa-2010-09-01.png =================================================================== (Binary files differ) Property changes on: projects/articles/crypto2011/direct-users-2011-04-01-300-sa-2010-09-01.png ___________________________________________________________________ Added: svn:mime-type + application/octet-stream Added: projects/articles/crypto2011/direct-users-2011-04-01-300-tn-2010-12-01.png =================================================================== (Binary files differ) Property changes on: projects/articles/crypto2011/direct-users-2011-04-01-300-tn-2010-12-01.png ___________________________________________________________________ Added: svn:mime-type + application/octet-stream

1 0

[tor/master] Merge remote-tracking branch 'origin/maint-0.2.1' into maint-0.2.2
by nickm＠torproject.org 28 May '11

28 May '11

commit 1f18b5a5d532449f46a9c4b74d188870ea56d813 Merge: c319949 f43aceb Author: Nick Mathewson <nickm(a)torproject.org> Date: Sat May 28 02:13:14 2011 -0400 Merge remote-tracking branch 'origin/maint-0.2.1' into maint-0.2.2 changes/bug2574 | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-)

1 0

[tor/master] Fix typo in changes/bug2574. Thanks, rransom
by nickm＠torproject.org 28 May '11

28 May '11

commit f43aceb0f1b10d71d2e99e323668ac35327e286b Author: Nick Mathewson <nickm(a)torproject.org> Date: Sat May 28 02:13:04 2011 -0400 Fix typo in changes/bug2574. Thanks, rransom --- changes/bug2574 | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-) diff --git a/changes/bug2574 b/changes/bug2574 index 32f4ae4..5cf2dae 100644 --- a/changes/bug2574 +++ b/changes/bug2574 @@ -1,2 +1,3 @@ o Minor features: - - Allow nameserves with IPv6 address. Fixes bug 2574. + - Allow nameservers with IPv6 address. Fixes bug 2574. +

1 0

[tor/master] Merge remote-tracking branch 'origin/maint-0.2.2'
by nickm＠torproject.org 28 May '11

28 May '11

commit e676db656da1c3911f0667faa4fd2396db1c9e8f Merge: 285cf99 1f18b5a Author: Nick Mathewson <nickm(a)torproject.org> Date: Sat May 28 02:13:25 2011 -0400 Merge remote-tracking branch 'origin/maint-0.2.2' changes/bug2574 | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-)

1 0