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.8 2003/05/03 05:31:07 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]);/* 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 */
          (hop == chainlen-1 || !badchains[thischain[hop+1]][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;
  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;
    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	rabbi	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	weaselp	500	$Id: chain.c,v 1.8 2003/05/03 05:31:07 weaselp Exp $ */
10	rabbi	1
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	weaselp	500	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	rabbi	1	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	weaselp	332	#if 0
121	rabbi	1	else if (isdigit(chain->data[j]))
122			k = atoi(chain->data + j);
123	rabbi	262	#endif /* 0 */
124	rabbi	1	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	weaselp	493	if (feedback != NULL) {
144			buf_appendf(feedback, "No such remailer: %b", selected);
145			buf_nl(feedback);
146			}
147	weaselp	332	#if 0
148	rabbi	1	k = 0;
149	rabbi	262	#else /* end of 0 */
150	rabbi	1	len = -1;
151			goto end;
152	rabbi	262	#endif /* else not 0 */
153	rabbi	1	}
154			hop[len++] = k;
155	rabbi	26	if (len >= 20) { /* array passed in is has length 20 */
156	weaselp	493	if (feedback != NULL) {
157			buf_appends(feedback, "Chain too long.\n");
158			}
159	rabbi	1	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	weaselp	500	int chain_randfinal(int type, REMAILER *remailer, int badchains[MAXREM][MAXREM], int maxrem, int rtype, int secondtolasthop)
172	rabbi	1	{
173			int num = 0;
174			int i;
175			int t;
176	weaselp	500	int select[MAXREM];
177	rabbi	1
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	weaselp	500	select[i] =
185			((remailer[i].flags.mix && rtype == 0) \|\| /* remailer supports type */
186	rabbi	1	(remailer[i].flags.pgp && remailer[i].flags.ek && rtype == 1) \|\|
187			(remailer[i].flags.newnym && rtype == 2)) &&
188	weaselp	500	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) \|\| !badchains[secondtolasthop][i]);/* we only have hop or the previous one can send to this (may be random) */
194			num += select[i];
195	rabbi	1	}
196			if (num == 0)
197			i = -1;
198			else {
199			do
200	weaselp	499	i = rnd_number(maxrem - 1) + 1;
201	weaselp	500	while (!select[i]);
202	rabbi	1	}
203			return (i);
204			}
205
206	weaselp	500	int chain_rand(REMAILER *remailer, int badchains[MAXREM][MAXREM], int maxrem,
207	rabbi	1	int thischain[], int chainlen, int t)
208			/* set random chain. returns 0 if not random, 1 if random, -1 on error */
209	weaselp	500	/* t... 0 for mixmaster Type II
210			* 1 for cypherpunk Type I
211			*/
212	rabbi	1	{
213			int hop;
214			int err = 0;
215
216			assert(t == 0 \|\| t == 1);
217
218			for (hop = 0; hop < chainlen; hop++)
219			if (thischain[hop] == 0) {
220			int select[MAXREM];
221			int randavail = 0;
222			int i;
223
224			err = 1;
225	weaselp	500	if (hop > 0)
226			assert(thischain[hop-1]); /* we already should have chosen a remailer after this one */
227			for (i = 1; i < maxrem; i++) {
228			select[i] = ((remailer[i].flags.mix && t == 0) \|\| /* remailer supports type */
229	rabbi	1	(remailer[i].flags.pgp && remailer[i].flags.ek && t == 1))
230	weaselp	500	&& remailer[i].info[t].reliability >= 100 * MINREL && /* remailer has sufficient reliability */
231			!remailer[i].flags.star_ex && /* remailer is not excluded from random selection */
232			remailer[i].info[t].latency <= MAXLAT && /* remailer has small enough latency */
233			!badchains[i][0] && !badchains[i][thischain[hop-1]] && /* remailer can send to the next one */
234			(hop == chainlen-1 \|\| !badchains[thischain[hop+1]][i]);/* we are at the first hop or the previous one can send to this (may be random) */
235			randavail += select[i];
236			}
237	rabbi	1
238			for (i = hop - DISTANCE; i <= hop + DISTANCE; i++)
239	weaselp	500	if (i >= 0 && i < chainlen && select[thischain[i]]) {
240			select[thischain[i]] = 0;
241			randavail--;
242			}
243	rabbi	1
244	weaselp	500
245	rabbi	1	if (randavail < 1) {
246			err = -1;
247			goto end;
248			}
249			do
250			thischain[hop] = rnd_number(maxrem - 1) + 1;
251			while (!select[thischain[hop]]);
252			}
253			end:
254			return (err);
255			}
256
257			int mix_encrypt(int type, BUFFER message, char chainstr, int numcopies,
258			BUFFER *chainlist)
259			{
260			return (mix2_encrypt(type, message, chainstr, numcopies, chainlist));
261			}
262
263			/* float chain_reliablity(char *chain, int chaintype,
264	weaselp	332	char *reliability_string);
265	rabbi	1	*
266			* Compute reliablity of a chain.
267			*
268			* We get the reliablity of the chain by multiplying the reliablity of
269			* every remailer in the chain. The return value is the reliablity of
270			* the chain, or a negative number if the reliablity can not be
271			* calculated. There are two reasons why may not be able to calculated
272			* the reliablity: A remailer in the chain is selected randomly, or we
273			* don't have statistics about one of the remailers in the chain.
274			* remailer_type indicates the remailer type:
275			* 0 = Mixmaster, 1 = Cypherpunk
276			*
277			* If reliability_string is non-NULL, the reliability is also returned
278			* as a string in this variable. The size of the string must be at
279			* least 9 characters!
280			*
281			* This function has been added by Gerd Beuster. (gb@uni-koblenz.de)
282			--------------------------------------------------------------------/
283
284			float chain_reliability(char *chain, int chaintype,
285			char *reliability_string){
286	weaselp	332
287	rabbi	1	float acc_reliability = 1; /* Accumulated reliablity */
288			char name_start, name_end; /* temporary pointers used
289			in string scanning */
290			char remailer_name[20]; /* The length of the array is taken from mix3.h. */
291			int error = 0;
292			int maxrem;
293			int i;
294			REMAILER remailer[MAXREM];
295	weaselp	500	int badchains[MAXREM][MAXREM];
296	rabbi	1
297			/* chaintype 0=mix 1=ek 2=newnym */
298			assert((chaintype == 0) \|\| (chaintype == 1));
299	weaselp	500	maxrem = (chaintype == 0 ? mix2_rlist(remailer, badchains) : t1_rlist(remailer, badchains));
300	rabbi	1
301			/* Dissect chain */
302			name_start = chain;
303			name_end = chain;
304			while(name_end != '\0'){ / While string not scanned completely */
305			do /* Get next remailer */
306			name_end+=sizeof(char);
307			while( (name_end != ',') && (name_end != '\0'));
308			strncpy(remailer_name, name_start,
309			(name_end - name_start) / sizeof(char) + 1*sizeof(char));
310			remailer_name[name_end-name_start]='\0';
311			/* Lookup reliablity for remailer remailer_name */
312			for(i=0;
313			(i < maxrem) && (strcmp(remailer[i].name, remailer_name) != 0);
314			i++);
315			if(!strcmp(remailer[i].name, remailer_name)) /* Found it! */
316			acc_reliability *=
317			((float) remailer[i].info[chaintype].reliability) / 10000;
318			else
319			error = 1; /* Did not find this remailer. We can't calculate
320			the reliablity for the whole chain. */
321			name_start = name_end+sizeof(char);
322			}
323
324			if(error \|\| (name_start==name_end))
325			acc_reliability = -1;
326
327			/* Convert reliability into string, if appropriate */
328			if(reliability_string){
329			if(acc_reliability < 0)
330			sprintf(reliability_string, " n/a ");
331			else{
332			sprintf(reliability_string, "%6.2f", acc_reliability*100);
333			(reliability_string+6sizeof(char)) = '%';
334			}
335			}
336	weaselp	332
337	rabbi	1	return acc_reliability;
338			}
339	weaselp	332