Mix/Src/chain.c

/* Mixmaster version 3  --  (C) 1999 Anonymizer Inc.

   Mixmaster may be redistributed and modified under certain conditions.
   This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF
   ANY KIND, either express or implied. See the file COPYRIGHT for
   details.

   Prepare messages for remailer chain
   $Id: chain.c,v 1.10 2003/05/03 06:15:09 weaselp Exp $ */


#include "mix3.h"
#include <string.h>
#include <ctype.h>
#include <assert.h>
#include <stdlib.h>

void clienterr(BUFFER *msgbuf, char *err)
{
  if (msgbuf) {
    buf_sets(msgbuf, "Error: ");
    buf_appends(msgbuf, err);
  } else
    errlog(ERRORMSG, "%s\n", err);
}

void parse_badchains(int badchains[MAXREM][MAXREM], char *file, char *startindicator, REMAILER *remailer, int maxrem) {
  int i,j;
  FILE *list;
  char line[LINELEN];

  if (!badchains)
    return;

  for (i = 0; i < maxrem; i++ )
    for (j = 0; j < maxrem; j++ )
      badchains[i][j] = 0;
  list = mix_openfile(TYPE2REL, "r");
  if (list != NULL) {
    while (fgets(line, sizeof(line), list) != NULL &&
      !strleft(line, startindicator)) ;
    while (fgets(line, sizeof(line), list) != NULL &&
      strleft(line, "(")) {
      char *left, *right, *tmp;
      int lefti, righti;

      left = line + 1;
      while (*left == ' ')
        left ++;

      tmp = left + 1;
      while (*tmp != ' ' && *tmp != '\0' && *tmp != ')')
        tmp ++;
      if (*tmp == '\0' || *tmp == ')')
        /* parsing this line failed */
        continue;
      *tmp = '\0';

      right = tmp+1;
      while (*right == ' ')
        right ++;
      tmp = right + 1;
      while (*tmp != ' ' && *tmp != '\0' && *tmp != ')')
        tmp ++;
      if (*tmp == '\0')
        /* parsing this line failed */
        continue;
      *tmp = '\0';

      lefti = -1;
      righti = -1;
      for (i = 1; i < maxrem; i++) {
        if (strcmp(remailer[i].name, left) == 0)
          lefti = i;
        if (strcmp(remailer[i].name, right) == 0)
          righti = i;
      }
      if (strcmp(left, "*") == 0)
        lefti = 0;
      if (strcmp(right, "*") == 0)
        righti = 0;

      if (lefti == -1 || righti == -1)
        /* we don't know about one or both remailers */
        continue;
      badchains[lefti][righti] = 1;
    }
  }
  fclose(list);
}


int chain_select(int hop[], char *chainstr, int maxrem, REMAILER *remailer,
                 int type, BUFFER *feedback)
{
  int len = 0;
  int i, j, k;
  BUFFER *chain, *selected, *addr;
  chain = buf_new();
  selected = buf_new();
  addr = buf_new();

  if (chainstr == NULL || chainstr[0] == '\0')
    buf_sets(chain, CHAIN);
  else
    buf_sets(chain, chainstr);

  /* put the chain backwards: final hop is in hop[0] */

  for (i = chain->length; i >= 0; i--)
    if (i == 0 || chain->data[i - 1] <= ' ' || chain->data[i - 1] == ','
        || chain->data[i - 1] == ';' || chain->data[i - 1] == ':') {
      for (j = i; isspace(chain->data[j]);)     /* ignore whitespace */
        j++;
      if (chain->data[j] == '\0')
        break;

      if (chain->data[j] == '*')
        k = 0;
#if 0
      else if (isdigit(chain->data[j]))
        k = atoi(chain->data + j);
#endif /* 0 */
      else {
        buf_sets(selected, chain->data + j);
        rfc822_addr(selected, addr);
        buf_clear(selected);
        buf_getline(addr, selected);
        if (!selected->length)
          buf_sets(selected, chain->data + j);

        for (k = 0; k < maxrem; k++)
          if (((remailer[k].flags.mix && type == 0) ||
               (remailer[k].flags.cpunk && type == 1) ||
               (remailer[k].flags.newnym && type == 2)) &&
              (streq(remailer[k].name, selected->data) ||
               strieq(remailer[k].addr, selected->data) ||
               (selected->data[0] == '@' && strifind(remailer[k].addr,
                                            selected->data))))
            break;
      }
      if (k < 0 || k >= maxrem) {
        if (feedback != NULL) {
                buf_appendf(feedback, "No such remailer: %b", selected);
                buf_nl(feedback);
        }
#if 0
        k = 0;
#else /* end of 0 */
        len = -1;
        goto end;
#endif /* else not 0 */
      }
      hop[len++] = k;
      if (len >= 20) {          /* array passed in is has length 20 */
        if (feedback != NULL) {
                buf_appends(feedback, "Chain too long.\n");
        }
        break;
      }
      if (i > 0)
        chain->data[i - 1] = '\0';
    }
end:
  buf_free(chain);
  buf_free(selected);
  buf_free(addr);
  return len;
}

int chain_randfinal(int type, REMAILER *remailer, int badchains[MAXREM][MAXREM], int maxrem, int rtype, int secondtolasthop)
{
  int num = 0;
  int i;
  int t;
  int select[MAXREM];

  t = rtype;
  if (rtype == 2)
    t = 1;

  /* select a random final hop */
  for (i = 1; i < maxrem; i++) {
    select[i] = 
       ((remailer[i].flags.mix && rtype == 0) ||             /* remailer supports type */
         (remailer[i].flags.pgp && remailer[i].flags.ek && rtype == 1) ||
         (remailer[i].flags.newnym && rtype == 2)) &&
        remailer[i].info[t].reliability >= 100 * RELFINAL && /* remailer has sufficient reliability */
        remailer[i].info[t].latency <= MAXLAT &&             /* remailer has small enough latency */
        (type == MSG_NULL || !remailer[i].flags.middle) &&   /* remailer is not middleman */
        !remailer[i].flags.star_ex &&                        /* remailer is not excluded from random selection */
        (remailer[i].flags.post || type != MSG_POST) &&      /* remailer supports post when this is a post */
        ((secondtolasthop == -1) ||
           (!badchains[secondtolasthop][i] &&
            !badchains[secondtolasthop][0] &&
            !badchains[0][i]));/* we only have hop or the previous one can send to this (may be random) */
    num += select[i];
  }
  if (num == 0)
    i = -1;
  else {
    do
      i = rnd_number(maxrem - 1) + 1;
    while (!select[i]);
  }
  return (i);
}

int chain_rand(REMAILER *remailer, int badchains[MAXREM][MAXREM], int maxrem,
               int thischain[], int chainlen, int t)
     /* set random chain. returns 0 if not random, 1 if random, -1 on error */
/* t... 0 for mixmaster Type II
 *      1 for cypherpunk Type I
 */
{
  int hop;
  int err = 0;

  assert(t == 0 || t == 1);

  for (hop = 0; hop < chainlen; hop++)
    if (thischain[hop] == 0) {
      int select[MAXREM];
      int randavail = 0;
      int i;

      err = 1;
      if (hop > 0)
        assert(thischain[hop-1]); /* we already should have chosen a remailer after this one */
      for (i = 1; i < maxrem; i++) {
        select[i] = ((remailer[i].flags.mix && t == 0) ||        /* remailer supports type */
                     (remailer[i].flags.pgp && remailer[i].flags.ek && t == 1))
          && remailer[i].info[t].reliability >= 100 * MINREL &&  /* remailer has sufficient reliability */
          !remailer[i].flags.star_ex &&                          /* remailer is not excluded from random selection */
          remailer[i].info[t].latency <= MAXLAT &&               /* remailer has small enough latency */
          !badchains[i][0] && !badchains[i][thischain[hop-1]] && /* remailer can send to the next one */
                              !badchains[0][thischain[hop-1]] &&
          (hop == chainlen-1 ||
             ( !badchains[thischain[hop+1]][i] &&
               !badchains[thischain[hop+1]][0] &&
               !badchains[0][i] ));/* we are at the first hop or the previous one can send to this (may be random) */
        randavail += select[i];
      }

      for (i = hop - DISTANCE; i <= hop + DISTANCE; i++)
        if (i >= 0 && i < chainlen && select[thischain[i]]) {
          select[thischain[i]] = 0;
          randavail--;
        }


      if (randavail < 1) {
        err = -1;
        goto end;
      }
      do
        thischain[hop] = rnd_number(maxrem - 1) + 1;
      while (!select[thischain[hop]]);
    }
end:
  return (err);
}

int mix_encrypt(int type, BUFFER *message, char *chainstr, int numcopies,
                BUFFER *chainlist)
{
  return (mix2_encrypt(type, message, chainstr, numcopies, chainlist));
}

/* float chain_reliablity(char *chain, int chaintype,
                          char *reliability_string);
 *
 * Compute reliablity of a chain.
 *
 * We get the reliablity of the chain by multiplying the reliablity of
 * every remailer in the chain. The return value is the reliablity of
 * the chain, or a negative number if the reliablity can not be
 * calculated. There are two reasons why may not be able to calculated
 * the reliablity: A remailer in the chain is selected randomly, or we
 * don't have statistics about one of the remailers in the chain.
 * remailer_type indicates the remailer type:
 * 0 = Mixmaster, 1 = Cypherpunk
 *
 * If reliability_string is non-NULL, the reliability is also returned
 * as a string in this variable. The size of the string must be at
 * least 9 characters!
 *
 * This function has been added by Gerd Beuster. (gb@uni-koblenz.de)
 *--------------------------------------------------------------------*/

float chain_reliability(char *chain, int chaintype,
                        char *reliability_string){

  float acc_reliability = 1; /* Accumulated reliablity */
  char *name_start, *name_end; /* temporary pointers used
                                 in string scanning */
  char remailer_name[20]; /* The length of the array is taken from mix3.h. */
  int error = 0;
  int maxrem;
  int i;
  int previous = -1;
  REMAILER remailer[MAXREM];
  int badchains[MAXREM][MAXREM];

  /* chaintype 0=mix 1=ek 2=newnym */
  assert((chaintype == 0) || (chaintype == 1));
  maxrem = (chaintype == 0 ? mix2_rlist(remailer, badchains) : t1_rlist(remailer, badchains));

  /* Dissect chain */
  name_start = chain;
  name_end = chain;
  while(*name_end != '\0'){ /* While string not scanned completely */
    do /* Get next remailer */
      name_end+=sizeof(char);
    while( (*name_end != ',') && (*name_end != '\0'));
    strncpy(remailer_name, name_start,
            (name_end - name_start) / sizeof(char) + 1*sizeof(char));
    remailer_name[name_end-name_start]='\0';
    /* Lookup reliablity for remailer remailer_name */
    for(i=0;
        (i < maxrem) && (strcmp(remailer[i].name, remailer_name) != 0);
        i++);
    if(!strcmp(remailer[i].name, remailer_name)) { /* Found it! */
      acc_reliability *=
        ((float) remailer[i].info[chaintype].reliability) / 10000;
      if (previous != -1) {
        if (badchains[previous][i] || badchains[0][i])
          acc_reliability = 0;
      }
      previous = i;
    } else
      error = 1; /* Did not find this remailer. We can't calculate
                    the reliablity for the whole chain. */
    name_start = name_end+sizeof(char);
  }

  if(error || (name_start==name_end))
    acc_reliability = -1;

  /* Convert reliability into string, if appropriate */
  if(reliability_string){
    if(acc_reliability < 0)
      sprintf(reliability_string, "  n/a  ");
    else{
      sprintf(reliability_string, "%6.2f", acc_reliability*100);
      *(reliability_string+6*sizeof(char)) = '%';
    }
  }

  return acc_reliability;
}

1	/* Mixmaster version 3 -- (C) 1999 Anonymizer Inc.
2
3	Mixmaster may be redistributed and modified under certain conditions.
4	This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF
5	ANY KIND, either express or implied. See the file COPYRIGHT for
6	details.
7
8	Prepare messages for remailer chain
9	$Id: chain.c,v 1.10 2003/05/03 06:15:09 weaselp Exp $ */
10
11
12	#include "mix3.h"
13	#include <string.h>
14	#include <ctype.h>
15	#include <assert.h>
16	#include <stdlib.h>
17
18	void clienterr(BUFFER msgbuf, char err)
19	{
20	if (msgbuf) {
21	buf_sets(msgbuf, "Error: ");
22	buf_appends(msgbuf, err);
23	} else
24	errlog(ERRORMSG, "%s\n", err);
25	}
26
27	void parse_badchains(int badchains[MAXREM][MAXREM], char file, char startindicator, REMAILER *remailer, int maxrem) {
28	int i,j;
29	FILE *list;
30	char line[LINELEN];
31
32	if (!badchains)
33	return;
34
35	for (i = 0; i < maxrem; i++ )
36	for (j = 0; j < maxrem; j++ )
37	badchains[i][j] = 0;
38	list = mix_openfile(TYPE2REL, "r");
39	if (list != NULL) {
40	while (fgets(line, sizeof(line), list) != NULL &&
41	!strleft(line, startindicator)) ;
42	while (fgets(line, sizeof(line), list) != NULL &&
43	strleft(line, "(")) {
44	char left, right, *tmp;
45	int lefti, righti;
46
47	left = line + 1;
48	while (*left == ' ')
49	left ++;
50
51	tmp = left + 1;
52	while (tmp != ' ' && tmp != '\0' && *tmp != ')')
53	tmp ++;
54	if (tmp == '\0' \|\| tmp == ')')
55	/* parsing this line failed */
56	continue;
57	*tmp = '\0';
58
59	right = tmp+1;
60	while (*right == ' ')
61	right ++;
62	tmp = right + 1;
63	while (tmp != ' ' && tmp != '\0' && *tmp != ')')
64	tmp ++;
65	if (*tmp == '\0')
66	/* parsing this line failed */
67	continue;
68	*tmp = '\0';
69
70	lefti = -1;
71	righti = -1;
72	for (i = 1; i < maxrem; i++) {
73	if (strcmp(remailer[i].name, left) == 0)
74	lefti = i;
75	if (strcmp(remailer[i].name, right) == 0)
76	righti = i;
77	}
78	if (strcmp(left, "*") == 0)
79	lefti = 0;
80	if (strcmp(right, "*") == 0)
81	righti = 0;
82
83	if (lefti == -1 \|\| righti == -1)
84	/* we don't know about one or both remailers */
85	continue;
86	badchains[lefti][righti] = 1;
87	}
88	}
89	fclose(list);
90	}
91
92
93	int chain_select(int hop[], char chainstr, int maxrem, REMAILER remailer,
94	int type, BUFFER *feedback)
95	{
96	int len = 0;
97	int i, j, k;
98	BUFFER chain, selected, *addr;
99	chain = buf_new();
100	selected = buf_new();
101	addr = buf_new();
102
103	if (chainstr == NULL \|\| chainstr[0] == '\0')
104	buf_sets(chain, CHAIN);
105	else
106	buf_sets(chain, chainstr);
107
108	/* put the chain backwards: final hop is in hop[0] */
109
110	for (i = chain->length; i >= 0; i--)
111	if (i == 0 \|\| chain->data[i - 1] <= ' ' \|\| chain->data[i - 1] == ','
112	\|\| chain->data[i - 1] == ';' \|\| chain->data[i - 1] == ':') {
113	for (j = i; isspace(chain->data[j]);) /* ignore whitespace */
114	j++;
115	if (chain->data[j] == '\0')
116	break;
117
118	if (chain->data[j] == '*')
119	k = 0;
120	#if 0
121	else if (isdigit(chain->data[j]))
122	k = atoi(chain->data + j);
123	#endif /* 0 */
124	else {
125	buf_sets(selected, chain->data + j);
126	rfc822_addr(selected, addr);
127	buf_clear(selected);
128	buf_getline(addr, selected);
129	if (!selected->length)
130	buf_sets(selected, chain->data + j);
131
132	for (k = 0; k < maxrem; k++)
133	if (((remailer[k].flags.mix && type == 0) \|\|
134	(remailer[k].flags.cpunk && type == 1) \|\|
135	(remailer[k].flags.newnym && type == 2)) &&
136	(streq(remailer[k].name, selected->data) \|\|
137	strieq(remailer[k].addr, selected->data) \|\|
138	(selected->data[0] == '@' && strifind(remailer[k].addr,
139	selected->data))))
140	break;
141	}
142	if (k < 0 \|\| k >= maxrem) {
143	if (feedback != NULL) {
144	buf_appendf(feedback, "No such remailer: %b", selected);
145	buf_nl(feedback);
146	}
147	#if 0
148	k = 0;
149	#else /* end of 0 */
150	len = -1;
151	goto end;
152	#endif /* else not 0 */
153	}
154	hop[len++] = k;
155	if (len >= 20) { /* array passed in is has length 20 */
156	if (feedback != NULL) {
157	buf_appends(feedback, "Chain too long.\n");
158	}
159	break;
160	}
161	if (i > 0)
162	chain->data[i - 1] = '\0';
163	}
164	end:
165	buf_free(chain);
166	buf_free(selected);
167	buf_free(addr);
168	return len;
169	}
170
171	int chain_randfinal(int type, REMAILER *remailer, int badchains[MAXREM][MAXREM], int maxrem, int rtype, int secondtolasthop)
172	{
173	int num = 0;
174	int i;
175	int t;
176	int select[MAXREM];
177
178	t = rtype;
179	if (rtype == 2)
180	t = 1;
181
182	/* select a random final hop */
183	for (i = 1; i < maxrem; i++) {
184	select[i] =
185	((remailer[i].flags.mix && rtype == 0) \|\| /* remailer supports type */
186	(remailer[i].flags.pgp && remailer[i].flags.ek && rtype == 1) \|\|
187	(remailer[i].flags.newnym && rtype == 2)) &&
188	remailer[i].info[t].reliability >= 100 * RELFINAL && /* remailer has sufficient reliability */
189	remailer[i].info[t].latency <= MAXLAT && /* remailer has small enough latency */
190	(type == MSG_NULL \|\| !remailer[i].flags.middle) && /* remailer is not middleman */
191	!remailer[i].flags.star_ex && /* remailer is not excluded from random selection */
192	(remailer[i].flags.post \|\| type != MSG_POST) && /* remailer supports post when this is a post */
193	((secondtolasthop == -1) \|\|
194	(!badchains[secondtolasthop][i] &&
195	!badchains[secondtolasthop][0] &&
196	!badchains[0][i]));/* we only have hop or the previous one can send to this (may be random) */
197	num += select[i];
198	}
199	if (num == 0)
200	i = -1;
201	else {
202	do
203	i = rnd_number(maxrem - 1) + 1;
204	while (!select[i]);
205	}
206	return (i);
207	}
208
209	int chain_rand(REMAILER *remailer, int badchains[MAXREM][MAXREM], int maxrem,
210	int thischain[], int chainlen, int t)
211	/* set random chain. returns 0 if not random, 1 if random, -1 on error */
212	/* t... 0 for mixmaster Type II
213	* 1 for cypherpunk Type I
214	*/
215	{
216	int hop;
217	int err = 0;
218
219	assert(t == 0 \|\| t == 1);
220
221	for (hop = 0; hop < chainlen; hop++)
222	if (thischain[hop] == 0) {
223	int select[MAXREM];
224	int randavail = 0;
225	int i;
226
227	err = 1;
228	if (hop > 0)
229	assert(thischain[hop-1]); /* we already should have chosen a remailer after this one */
230	for (i = 1; i < maxrem; i++) {
231	select[i] = ((remailer[i].flags.mix && t == 0) \|\| /* remailer supports type */
232	(remailer[i].flags.pgp && remailer[i].flags.ek && t == 1))
233	&& remailer[i].info[t].reliability >= 100 * MINREL && /* remailer has sufficient reliability */
234	!remailer[i].flags.star_ex && /* remailer is not excluded from random selection */
235	remailer[i].info[t].latency <= MAXLAT && /* remailer has small enough latency */
236	!badchains[i][0] && !badchains[i][thischain[hop-1]] && /* remailer can send to the next one */
237	!badchains[0][thischain[hop-1]] &&
238	(hop == chainlen-1 \|\|
239	( !badchains[thischain[hop+1]][i] &&
240	!badchains[thischain[hop+1]][0] &&
241	!badchains[0][i] ));/* we are at the first hop or the previous one can send to this (may be random) */
242	randavail += select[i];
243	}
244
245	for (i = hop - DISTANCE; i <= hop + DISTANCE; i++)
246	if (i >= 0 && i < chainlen && select[thischain[i]]) {
247	select[thischain[i]] = 0;
248	randavail--;
249	}
250
251
252	if (randavail < 1) {
253	err = -1;
254	goto end;
255	}
256	do
257	thischain[hop] = rnd_number(maxrem - 1) + 1;
258	while (!select[thischain[hop]]);
259	}
260	end:
261	return (err);
262	}
263
264	int mix_encrypt(int type, BUFFER message, char chainstr, int numcopies,
265	BUFFER *chainlist)
266	{
267	return (mix2_encrypt(type, message, chainstr, numcopies, chainlist));
268	}
269
270	/* float chain_reliablity(char *chain, int chaintype,
271	char *reliability_string);
272	*
273	* Compute reliablity of a chain.
274	*
275	* We get the reliablity of the chain by multiplying the reliablity of
276	* every remailer in the chain. The return value is the reliablity of
277	* the chain, or a negative number if the reliablity can not be
278	* calculated. There are two reasons why may not be able to calculated
279	* the reliablity: A remailer in the chain is selected randomly, or we
280	* don't have statistics about one of the remailers in the chain.
281	* remailer_type indicates the remailer type:
282	* 0 = Mixmaster, 1 = Cypherpunk
283	*
284	* If reliability_string is non-NULL, the reliability is also returned
285	* as a string in this variable. The size of the string must be at
286	* least 9 characters!
287	*
288	* This function has been added by Gerd Beuster. (gb@uni-koblenz.de)
289	--------------------------------------------------------------------/
290
291	float chain_reliability(char *chain, int chaintype,
292	char *reliability_string){
293
294	float acc_reliability = 1; /* Accumulated reliablity */
295	char name_start, name_end; /* temporary pointers used
296	in string scanning */
297	char remailer_name[20]; /* The length of the array is taken from mix3.h. */
298	int error = 0;
299	int maxrem;
300	int i;
301	int previous = -1;
302	REMAILER remailer[MAXREM];
303	int badchains[MAXREM][MAXREM];
304
305	/* chaintype 0=mix 1=ek 2=newnym */
306	assert((chaintype == 0) \|\| (chaintype == 1));
307	maxrem = (chaintype == 0 ? mix2_rlist(remailer, badchains) : t1_rlist(remailer, badchains));
308
309	/* Dissect chain */
310	name_start = chain;
311	name_end = chain;
312	while(name_end != '\0'){ / While string not scanned completely */
313	do /* Get next remailer */
314	name_end+=sizeof(char);
315	while( (name_end != ',') && (name_end != '\0'));
316	strncpy(remailer_name, name_start,
317	(name_end - name_start) / sizeof(char) + 1*sizeof(char));
318	remailer_name[name_end-name_start]='\0';
319	/* Lookup reliablity for remailer remailer_name */
320	for(i=0;
321	(i < maxrem) && (strcmp(remailer[i].name, remailer_name) != 0);
322	i++);
323	if(!strcmp(remailer[i].name, remailer_name)) { /* Found it! */
324	acc_reliability *=
325	((float) remailer[i].info[chaintype].reliability) / 10000;
326	if (previous != -1) {
327	if (badchains[previous][i] \|\| badchains[0][i])
328	acc_reliability = 0;
329	}
330	previous = i;
331	} else
332	error = 1; /* Did not find this remailer. We can't calculate
333	the reliablity for the whole chain. */
334	name_start = name_end+sizeof(char);
335	}
336
337	if(error \|\| (name_start==name_end))
338	acc_reliability = -1;
339
340	/* Convert reliability into string, if appropriate */
341	if(reliability_string){
342	if(acc_reliability < 0)
343	sprintf(reliability_string, " n/a ");
344	else{
345	sprintf(reliability_string, "%6.2f", acc_reliability*100);
346	(reliability_string+6sizeof(char)) = '%';
347	}
348	}
349
350	return acc_reliability;
351	}
352