circuitbuild.c 107 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128
  1. /* Copyright (c) 2001 Matej Pfajfar.
  2. * Copyright (c) 2001-2004, Roger Dingledine.
  3. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  4. * Copyright (c) 2007-2017, The Tor Project, Inc. */
  5. /* See LICENSE for licensing information */
  6. /**
  7. * \file circuitbuild.c
  8. *
  9. * \brief Implements the details of building circuits (by chosing paths,
  10. * constructing/sending create/extend cells, and so on).
  11. *
  12. * On the client side, this module handles launching circuits. Circuit
  13. * launches are srtarted from circuit_establish_circuit(), called from
  14. * circuit_launch_by_extend_info()). To choose the path the circuit will
  15. * take, onion_extend_cpath() calls into a maze of node selection functions.
  16. *
  17. * Once the circuit is ready to be launched, the first hop is treated as a
  18. * special case with circuit_handle_first_hop(), since it might need to open a
  19. * channel. As the channel opens, and later as CREATED and RELAY_EXTENDED
  20. * cells arrive, the client will invoke circuit_send_next_onion_skin() to send
  21. * CREATE or RELAY_EXTEND cells.
  22. *
  23. * On the server side, this module also handles the logic of responding to
  24. * RELAY_EXTEND requests, using circuit_extend().
  25. **/
  26. #define CIRCUITBUILD_PRIVATE
  27. #include "or.h"
  28. #include "bridges.h"
  29. #include "channel.h"
  30. #include "circpathbias.h"
  31. #define CIRCUITBUILD_PRIVATE
  32. #include "circuitbuild.h"
  33. #include "circuitlist.h"
  34. #include "circuitstats.h"
  35. #include "circuituse.h"
  36. #include "command.h"
  37. #include "config.h"
  38. #include "confparse.h"
  39. #include "connection.h"
  40. #include "connection_edge.h"
  41. #include "connection_or.h"
  42. #include "control.h"
  43. #include "crypto.h"
  44. #include "directory.h"
  45. #include "entrynodes.h"
  46. #include "hs_ntor.h"
  47. #include "main.h"
  48. #include "microdesc.h"
  49. #include "networkstatus.h"
  50. #include "nodelist.h"
  51. #include "onion.h"
  52. #include "onion_tap.h"
  53. #include "onion_fast.h"
  54. #include "policies.h"
  55. #include "relay.h"
  56. #include "rendcommon.h"
  57. #include "rephist.h"
  58. #include "router.h"
  59. #include "routerlist.h"
  60. #include "routerparse.h"
  61. #include "routerset.h"
  62. #include "transports.h"
  63. static channel_t * channel_connect_for_circuit(const tor_addr_t *addr,
  64. uint16_t port,
  65. const char *id_digest,
  66. const ed25519_public_key_t *ed_id);
  67. static int circuit_deliver_create_cell(circuit_t *circ,
  68. const create_cell_t *create_cell,
  69. int relayed);
  70. static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit,
  71. int is_hs_v3_rp_circuit);
  72. static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
  73. static int onion_extend_cpath(origin_circuit_t *circ);
  74. STATIC int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
  75. static int circuit_send_first_onion_skin(origin_circuit_t *circ);
  76. static int circuit_build_no_more_hops(origin_circuit_t *circ);
  77. static int circuit_send_intermediate_onion_skin(origin_circuit_t *circ,
  78. crypt_path_t *hop);
  79. static const node_t *choose_good_middle_server(uint8_t purpose,
  80. cpath_build_state_t *state,
  81. crypt_path_t *head,
  82. int cur_len);
  83. /** This function tries to get a channel to the specified endpoint,
  84. * and then calls command_setup_channel() to give it the right
  85. * callbacks.
  86. */
  87. static channel_t *
  88. channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port,
  89. const char *id_digest,
  90. const ed25519_public_key_t *ed_id)
  91. {
  92. channel_t *chan;
  93. chan = channel_connect(addr, port, id_digest, ed_id);
  94. if (chan) command_setup_channel(chan);
  95. return chan;
  96. }
  97. /** Search for a value for circ_id that we can use on <b>chan</b> for an
  98. * outbound circuit, until we get a circ_id that is not in use by any other
  99. * circuit on that conn.
  100. *
  101. * Return it, or 0 if can't get a unique circ_id.
  102. */
  103. STATIC circid_t
  104. get_unique_circ_id_by_chan(channel_t *chan)
  105. {
  106. /* This number is chosen somewhat arbitrarily; see comment below for more
  107. * info. When the space is 80% full, it gives a one-in-a-million failure
  108. * chance; when the space is 90% full, it gives a one-in-850 chance; and when
  109. * the space is 95% full, it gives a one-in-26 failure chance. That seems
  110. * okay, though you could make a case IMO for anything between N=32 and
  111. * N=256. */
  112. #define MAX_CIRCID_ATTEMPTS 64
  113. int in_use;
  114. unsigned n_with_circ = 0, n_pending_destroy = 0, n_weird_pending_destroy = 0;
  115. circid_t test_circ_id;
  116. circid_t attempts=0;
  117. circid_t high_bit, max_range, mask;
  118. int64_t pending_destroy_time_total = 0;
  119. int64_t pending_destroy_time_max = 0;
  120. tor_assert(chan);
  121. if (chan->circ_id_type == CIRC_ID_TYPE_NEITHER) {
  122. log_warn(LD_BUG,
  123. "Trying to pick a circuit ID for a connection from "
  124. "a client with no identity.");
  125. return 0;
  126. }
  127. max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15);
  128. mask = max_range - 1;
  129. high_bit = (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? max_range : 0;
  130. do {
  131. if (++attempts > MAX_CIRCID_ATTEMPTS) {
  132. /* Make sure we don't loop forever because all circuit IDs are used.
  133. *
  134. * Once, we would try until we had tried every possible circuit ID. But
  135. * that's quite expensive. Instead, we try MAX_CIRCID_ATTEMPTS random
  136. * circuit IDs, and then give up.
  137. *
  138. * This potentially causes us to give up early if our circuit ID space
  139. * is nearly full. If we have N circuit IDs in use, then we will reject
  140. * a new circuit with probability (N / max_range) ^ MAX_CIRCID_ATTEMPTS.
  141. * This means that in practice, a few percent of our circuit ID capacity
  142. * will go unused.
  143. *
  144. * The alternative here, though, is to do a linear search over the
  145. * whole circuit ID space every time we extend a circuit, which is
  146. * not so great either.
  147. */
  148. int64_t queued_destroys;
  149. char *m = rate_limit_log(&chan->last_warned_circ_ids_exhausted,
  150. approx_time());
  151. if (m == NULL)
  152. return 0; /* This message has been rate-limited away. */
  153. if (n_pending_destroy)
  154. pending_destroy_time_total /= n_pending_destroy;
  155. log_warn(LD_CIRC,"No unused circIDs found on channel %s wide "
  156. "circID support, with %u inbound and %u outbound circuits. "
  157. "Found %u circuit IDs in use by circuits, and %u with "
  158. "pending destroy cells. (%u of those were marked bogusly.) "
  159. "The ones with pending destroy cells "
  160. "have been marked unusable for an average of %ld seconds "
  161. "and a maximum of %ld seconds. This channel is %ld seconds "
  162. "old. Failing a circuit.%s",
  163. chan->wide_circ_ids ? "with" : "without",
  164. chan->num_p_circuits, chan->num_n_circuits,
  165. n_with_circ, n_pending_destroy, n_weird_pending_destroy,
  166. (long)pending_destroy_time_total,
  167. (long)pending_destroy_time_max,
  168. (long)(approx_time() - chan->timestamp_created),
  169. m);
  170. tor_free(m);
  171. if (!chan->cmux) {
  172. /* This warning should be impossible. */
  173. log_warn(LD_BUG, " This channel somehow has no cmux on it!");
  174. return 0;
  175. }
  176. /* analysis so far on 12184 suggests that we're running out of circuit
  177. IDs because it looks like we have too many pending destroy
  178. cells. Let's see how many we really have pending.
  179. */
  180. queued_destroys = circuitmux_count_queued_destroy_cells(chan,
  181. chan->cmux);
  182. log_warn(LD_CIRC, " Circuitmux on this channel has %u circuits, "
  183. "of which %u are active. It says it has "I64_FORMAT
  184. " destroy cells queued.",
  185. circuitmux_num_circuits(chan->cmux),
  186. circuitmux_num_active_circuits(chan->cmux),
  187. I64_PRINTF_ARG(queued_destroys));
  188. /* Change this into "if (1)" in order to get more information about
  189. * possible failure modes here. You'll need to know how to use gdb with
  190. * Tor: this will make Tor exit with an assertion failure if the cmux is
  191. * corrupt. */
  192. if (0)
  193. circuitmux_assert_okay(chan->cmux);
  194. channel_dump_statistics(chan, LOG_WARN);
  195. return 0;
  196. }
  197. do {
  198. crypto_rand((char*) &test_circ_id, sizeof(test_circ_id));
  199. test_circ_id &= mask;
  200. } while (test_circ_id == 0);
  201. test_circ_id |= high_bit;
  202. in_use = circuit_id_in_use_on_channel(test_circ_id, chan);
  203. if (in_use == 1)
  204. ++n_with_circ;
  205. else if (in_use == 2) {
  206. time_t since_when;
  207. ++n_pending_destroy;
  208. since_when =
  209. circuit_id_when_marked_unusable_on_channel(test_circ_id, chan);
  210. if (since_when) {
  211. time_t waiting = approx_time() - since_when;
  212. pending_destroy_time_total += waiting;
  213. if (waiting > pending_destroy_time_max)
  214. pending_destroy_time_max = waiting;
  215. } else {
  216. ++n_weird_pending_destroy;
  217. }
  218. }
  219. } while (in_use);
  220. return test_circ_id;
  221. }
  222. /** If <b>verbose</b> is false, allocate and return a comma-separated list of
  223. * the currently built elements of <b>circ</b>. If <b>verbose</b> is true, also
  224. * list information about link status in a more verbose format using spaces.
  225. * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
  226. * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
  227. * names.
  228. */
  229. static char *
  230. circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
  231. {
  232. crypt_path_t *hop;
  233. smartlist_t *elements;
  234. const char *states[] = {"closed", "waiting for keys", "open"};
  235. char *s;
  236. elements = smartlist_new();
  237. if (verbose) {
  238. const char *nickname = build_state_get_exit_nickname(circ->build_state);
  239. smartlist_add_asprintf(elements, "%s%s circ (length %d%s%s):",
  240. circ->build_state->is_internal ? "internal" : "exit",
  241. circ->build_state->need_uptime ? " (high-uptime)" : "",
  242. circ->build_state->desired_path_len,
  243. circ->base_.state == CIRCUIT_STATE_OPEN ? "" : ", last hop ",
  244. circ->base_.state == CIRCUIT_STATE_OPEN ? "" :
  245. (nickname?nickname:"*unnamed*"));
  246. }
  247. hop = circ->cpath;
  248. do {
  249. char *elt;
  250. const char *id;
  251. const node_t *node;
  252. if (!hop)
  253. break;
  254. if (!verbose && hop->state != CPATH_STATE_OPEN)
  255. break;
  256. if (!hop->extend_info)
  257. break;
  258. id = hop->extend_info->identity_digest;
  259. if (verbose_names) {
  260. elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1);
  261. if ((node = node_get_by_id(id))) {
  262. node_get_verbose_nickname(node, elt);
  263. } else if (is_legal_nickname(hop->extend_info->nickname)) {
  264. elt[0] = '$';
  265. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  266. elt[HEX_DIGEST_LEN+1]= '~';
  267. strlcpy(elt+HEX_DIGEST_LEN+2,
  268. hop->extend_info->nickname, MAX_NICKNAME_LEN+1);
  269. } else {
  270. elt[0] = '$';
  271. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  272. }
  273. } else { /* ! verbose_names */
  274. elt = tor_malloc(HEX_DIGEST_LEN+2);
  275. elt[0] = '$';
  276. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  277. }
  278. tor_assert(elt);
  279. if (verbose) {
  280. tor_assert(hop->state <= 2);
  281. smartlist_add_asprintf(elements,"%s(%s)",elt,states[hop->state]);
  282. tor_free(elt);
  283. } else {
  284. smartlist_add(elements, elt);
  285. }
  286. hop = hop->next;
  287. } while (hop != circ->cpath);
  288. s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
  289. SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  290. smartlist_free(elements);
  291. return s;
  292. }
  293. /** If <b>verbose</b> is false, allocate and return a comma-separated
  294. * list of the currently built elements of <b>circ</b>. If
  295. * <b>verbose</b> is true, also list information about link status in
  296. * a more verbose format using spaces.
  297. */
  298. char *
  299. circuit_list_path(origin_circuit_t *circ, int verbose)
  300. {
  301. return circuit_list_path_impl(circ, verbose, 0);
  302. }
  303. /** Allocate and return a comma-separated list of the currently built elements
  304. * of <b>circ</b>, giving each as a verbose nickname.
  305. */
  306. char *
  307. circuit_list_path_for_controller(origin_circuit_t *circ)
  308. {
  309. return circuit_list_path_impl(circ, 0, 1);
  310. }
  311. /** Log, at severity <b>severity</b>, the nicknames of each router in
  312. * <b>circ</b>'s cpath. Also log the length of the cpath, and the intended
  313. * exit point.
  314. */
  315. void
  316. circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
  317. {
  318. char *s = circuit_list_path(circ,1);
  319. tor_log(severity,domain,"%s",s);
  320. tor_free(s);
  321. }
  322. /** Tell the rep(utation)hist(ory) module about the status of the links
  323. * in <b>circ</b>. Hops that have become OPEN are marked as successfully
  324. * extended; the _first_ hop that isn't open (if any) is marked as
  325. * unable to extend.
  326. */
  327. /* XXXX Someday we should learn from OR circuits too. */
  328. void
  329. circuit_rep_hist_note_result(origin_circuit_t *circ)
  330. {
  331. crypt_path_t *hop;
  332. const char *prev_digest = NULL;
  333. hop = circ->cpath;
  334. if (!hop) /* circuit hasn't started building yet. */
  335. return;
  336. if (server_mode(get_options())) {
  337. const routerinfo_t *me = router_get_my_routerinfo();
  338. if (!me)
  339. return;
  340. prev_digest = me->cache_info.identity_digest;
  341. }
  342. do {
  343. const node_t *node = node_get_by_id(hop->extend_info->identity_digest);
  344. if (node) { /* Why do we check this? We know the identity. -NM XXXX */
  345. if (prev_digest) {
  346. if (hop->state == CPATH_STATE_OPEN)
  347. rep_hist_note_extend_succeeded(prev_digest, node->identity);
  348. else {
  349. rep_hist_note_extend_failed(prev_digest, node->identity);
  350. break;
  351. }
  352. }
  353. prev_digest = node->identity;
  354. } else {
  355. prev_digest = NULL;
  356. }
  357. hop=hop->next;
  358. } while (hop!=circ->cpath);
  359. }
  360. /** Return 1 iff every node in circ's cpath definitely supports ntor. */
  361. static int
  362. circuit_cpath_supports_ntor(const origin_circuit_t *circ)
  363. {
  364. crypt_path_t *head, *cpath;
  365. cpath = head = circ->cpath;
  366. do {
  367. /* if the extend_info is missing, we can't tell if it supports ntor */
  368. if (!cpath->extend_info) {
  369. return 0;
  370. }
  371. /* if the key is blank, it definitely doesn't support ntor */
  372. if (!extend_info_supports_ntor(cpath->extend_info)) {
  373. return 0;
  374. }
  375. cpath = cpath->next;
  376. } while (cpath != head);
  377. return 1;
  378. }
  379. /** Pick all the entries in our cpath. Stop and return 0 when we're
  380. * happy, or return -1 if an error occurs. */
  381. static int
  382. onion_populate_cpath(origin_circuit_t *circ)
  383. {
  384. int r = 0;
  385. /* onion_extend_cpath assumes these are non-NULL */
  386. tor_assert(circ);
  387. tor_assert(circ->build_state);
  388. while (r == 0) {
  389. r = onion_extend_cpath(circ);
  390. if (r < 0) {
  391. log_info(LD_CIRC,"Generating cpath hop failed.");
  392. return -1;
  393. }
  394. }
  395. /* The path is complete */
  396. tor_assert(r == 1);
  397. /* Does every node in this path support ntor? */
  398. int path_supports_ntor = circuit_cpath_supports_ntor(circ);
  399. /* We would like every path to support ntor, but we have to allow for some
  400. * edge cases. */
  401. tor_assert(circuit_get_cpath_len(circ));
  402. if (circuit_can_use_tap(circ)) {
  403. /* Circuits from clients to intro points, and hidden services to
  404. * rend points do not support ntor, because the hidden service protocol
  405. * does not include ntor onion keys. This is also true for Tor2web clients
  406. * and Single Onion Services. */
  407. return 0;
  408. }
  409. if (circuit_get_cpath_len(circ) == 1) {
  410. /* Allow for bootstrapping: when we're fetching directly from a fallback,
  411. * authority, or bridge, we have no way of knowing its ntor onion key
  412. * before we connect to it. So instead, we try connecting, and end up using
  413. * CREATE_FAST. */
  414. tor_assert(circ->cpath);
  415. tor_assert(circ->cpath->extend_info);
  416. const node_t *node = node_get_by_id(
  417. circ->cpath->extend_info->identity_digest);
  418. /* If we don't know the node and its descriptor, we must be bootstrapping.
  419. */
  420. if (!node || !node_has_descriptor(node)) {
  421. return 0;
  422. }
  423. }
  424. if (BUG(!path_supports_ntor)) {
  425. /* If we're building a multi-hop path, and it's not one of the HS or
  426. * bootstrapping exceptions, and it doesn't support ntor, something has
  427. * gone wrong. */
  428. return -1;
  429. }
  430. return 0;
  431. }
  432. /** Create and return a new origin circuit. Initialize its purpose and
  433. * build-state based on our arguments. The <b>flags</b> argument is a
  434. * bitfield of CIRCLAUNCH_* flags. */
  435. origin_circuit_t *
  436. origin_circuit_init(uint8_t purpose, int flags)
  437. {
  438. /* sets circ->p_circ_id and circ->p_chan */
  439. origin_circuit_t *circ = origin_circuit_new();
  440. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_CHAN_WAIT);
  441. circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
  442. circ->build_state->onehop_tunnel =
  443. ((flags & CIRCLAUNCH_ONEHOP_TUNNEL) ? 1 : 0);
  444. circ->build_state->need_uptime =
  445. ((flags & CIRCLAUNCH_NEED_UPTIME) ? 1 : 0);
  446. circ->build_state->need_capacity =
  447. ((flags & CIRCLAUNCH_NEED_CAPACITY) ? 1 : 0);
  448. circ->build_state->is_internal =
  449. ((flags & CIRCLAUNCH_IS_INTERNAL) ? 1 : 0);
  450. circ->base_.purpose = purpose;
  451. return circ;
  452. }
  453. /** Build a new circuit for <b>purpose</b>. If <b>exit</b>
  454. * is defined, then use that as your exit router, else choose a suitable
  455. * exit node.
  456. *
  457. * Also launch a connection to the first OR in the chosen path, if
  458. * it's not open already.
  459. */
  460. origin_circuit_t *
  461. circuit_establish_circuit(uint8_t purpose, extend_info_t *exit_ei, int flags)
  462. {
  463. origin_circuit_t *circ;
  464. int err_reason = 0;
  465. int is_hs_v3_rp_circuit = 0;
  466. if (flags & CIRCLAUNCH_IS_V3_RP) {
  467. is_hs_v3_rp_circuit = 1;
  468. }
  469. circ = origin_circuit_init(purpose, flags);
  470. if (onion_pick_cpath_exit(circ, exit_ei, is_hs_v3_rp_circuit) < 0 ||
  471. onion_populate_cpath(circ) < 0) {
  472. circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
  473. return NULL;
  474. }
  475. control_event_circuit_status(circ, CIRC_EVENT_LAUNCHED, 0);
  476. if ((err_reason = circuit_handle_first_hop(circ)) < 0) {
  477. circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
  478. return NULL;
  479. }
  480. return circ;
  481. }
  482. /** Return the guard state associated with <b>circ</b>, which may be NULL. */
  483. circuit_guard_state_t *
  484. origin_circuit_get_guard_state(origin_circuit_t *circ)
  485. {
  486. return circ->guard_state;
  487. }
  488. /** Start establishing the first hop of our circuit. Figure out what
  489. * OR we should connect to, and if necessary start the connection to
  490. * it. If we're already connected, then send the 'create' cell.
  491. * Return 0 for ok, -reason if circ should be marked-for-close. */
  492. int
  493. circuit_handle_first_hop(origin_circuit_t *circ)
  494. {
  495. crypt_path_t *firsthop;
  496. channel_t *n_chan;
  497. int err_reason = 0;
  498. const char *msg = NULL;
  499. int should_launch = 0;
  500. const or_options_t *options = get_options();
  501. firsthop = onion_next_hop_in_cpath(circ->cpath);
  502. tor_assert(firsthop);
  503. tor_assert(firsthop->extend_info);
  504. /* Some bridges are on private addresses. Others pass a dummy private
  505. * address to the pluggable transport, which ignores it.
  506. * Deny the connection if:
  507. * - the address is internal, and
  508. * - we're not connecting to a configured bridge, and
  509. * - we're not configured to allow extends to private addresses. */
  510. if (tor_addr_is_internal(&firsthop->extend_info->addr, 0) &&
  511. !extend_info_is_a_configured_bridge(firsthop->extend_info) &&
  512. !options->ExtendAllowPrivateAddresses) {
  513. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  514. "Client asked me to connect directly to a private address");
  515. return -END_CIRC_REASON_TORPROTOCOL;
  516. }
  517. /* now see if we're already connected to the first OR in 'route' */
  518. log_debug(LD_CIRC,"Looking for firsthop '%s'",
  519. fmt_addrport(&firsthop->extend_info->addr,
  520. firsthop->extend_info->port));
  521. n_chan = channel_get_for_extend(firsthop->extend_info->identity_digest,
  522. &firsthop->extend_info->ed_identity,
  523. &firsthop->extend_info->addr,
  524. &msg,
  525. &should_launch);
  526. if (!n_chan) {
  527. /* not currently connected in a useful way. */
  528. log_info(LD_CIRC, "Next router is %s: %s",
  529. safe_str_client(extend_info_describe(firsthop->extend_info)),
  530. msg?msg:"???");
  531. circ->base_.n_hop = extend_info_dup(firsthop->extend_info);
  532. if (should_launch) {
  533. if (circ->build_state->onehop_tunnel)
  534. control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR, 0);
  535. n_chan = channel_connect_for_circuit(
  536. &firsthop->extend_info->addr,
  537. firsthop->extend_info->port,
  538. firsthop->extend_info->identity_digest,
  539. &firsthop->extend_info->ed_identity);
  540. if (!n_chan) { /* connect failed, forget the whole thing */
  541. log_info(LD_CIRC,"connect to firsthop failed. Closing.");
  542. return -END_CIRC_REASON_CONNECTFAILED;
  543. }
  544. }
  545. log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
  546. /* return success. The onion/circuit/etc will be taken care of
  547. * automatically (may already have been) whenever n_chan reaches
  548. * OR_CONN_STATE_OPEN.
  549. */
  550. return 0;
  551. } else { /* it's already open. use it. */
  552. tor_assert(!circ->base_.n_hop);
  553. circ->base_.n_chan = n_chan;
  554. log_debug(LD_CIRC,"Conn open. Delivering first onion skin.");
  555. if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) {
  556. log_info(LD_CIRC,"circuit_send_next_onion_skin failed.");
  557. circ->base_.n_chan = NULL;
  558. return err_reason;
  559. }
  560. }
  561. return 0;
  562. }
  563. /** Find any circuits that are waiting on <b>or_conn</b> to become
  564. * open and get them to send their create cells forward.
  565. *
  566. * Status is 1 if connect succeeded, or 0 if connect failed.
  567. *
  568. * Close_origin_circuits is 1 if we should close all the origin circuits
  569. * through this channel, or 0 otherwise. (This happens when we want to retry
  570. * an older guard.)
  571. */
  572. void
  573. circuit_n_chan_done(channel_t *chan, int status, int close_origin_circuits)
  574. {
  575. smartlist_t *pending_circs;
  576. int err_reason = 0;
  577. tor_assert(chan);
  578. log_debug(LD_CIRC,"chan to %s, status=%d",
  579. channel_get_canonical_remote_descr(chan), status);
  580. pending_circs = smartlist_new();
  581. circuit_get_all_pending_on_channel(pending_circs, chan);
  582. SMARTLIST_FOREACH_BEGIN(pending_circs, circuit_t *, circ)
  583. {
  584. /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
  585. * leaving them in in case it's possible for the status of a circuit to
  586. * change as we're going down the list. */
  587. if (circ->marked_for_close || circ->n_chan || !circ->n_hop ||
  588. circ->state != CIRCUIT_STATE_CHAN_WAIT)
  589. continue;
  590. if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
  591. /* Look at addr/port. This is an unkeyed connection. */
  592. if (!channel_matches_extend_info(chan, circ->n_hop))
  593. continue;
  594. } else {
  595. /* We expected a key. See if it's the right one. */
  596. if (tor_memneq(chan->identity_digest,
  597. circ->n_hop->identity_digest, DIGEST_LEN))
  598. continue;
  599. }
  600. if (!status) { /* chan failed; close circ */
  601. log_info(LD_CIRC,"Channel failed; closing circ.");
  602. circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
  603. continue;
  604. }
  605. if (close_origin_circuits && CIRCUIT_IS_ORIGIN(circ)) {
  606. log_info(LD_CIRC,"Channel deprecated for origin circs; closing circ.");
  607. circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
  608. continue;
  609. }
  610. log_debug(LD_CIRC, "Found circ, sending create cell.");
  611. /* circuit_deliver_create_cell will set n_circ_id and add us to
  612. * chan_circuid_circuit_map, so we don't need to call
  613. * set_circid_chan here. */
  614. circ->n_chan = chan;
  615. extend_info_free(circ->n_hop);
  616. circ->n_hop = NULL;
  617. if (CIRCUIT_IS_ORIGIN(circ)) {
  618. if ((err_reason =
  619. circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ))) < 0) {
  620. log_info(LD_CIRC,
  621. "send_next_onion_skin failed; circuit marked for closing.");
  622. circuit_mark_for_close(circ, -err_reason);
  623. continue;
  624. /* XXX could this be bad, eg if next_onion_skin failed because conn
  625. * died? */
  626. }
  627. } else {
  628. /* pull the create cell out of circ->n_chan_create_cell, and send it */
  629. tor_assert(circ->n_chan_create_cell);
  630. if (circuit_deliver_create_cell(circ, circ->n_chan_create_cell, 1)<0) {
  631. circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
  632. continue;
  633. }
  634. tor_free(circ->n_chan_create_cell);
  635. circuit_set_state(circ, CIRCUIT_STATE_OPEN);
  636. }
  637. }
  638. SMARTLIST_FOREACH_END(circ);
  639. smartlist_free(pending_circs);
  640. }
  641. /** Find a new circid that isn't currently in use on the circ->n_chan
  642. * for the outgoing
  643. * circuit <b>circ</b>, and deliver the cell <b>create_cell</b> to this
  644. * circuit. If <b>relayed</b> is true, this is a create cell somebody
  645. * gave us via an EXTEND cell, so we shouldn't worry if we don't understand
  646. * it. Return -1 if we failed to find a suitable circid, else return 0.
  647. */
  648. static int
  649. circuit_deliver_create_cell(circuit_t *circ, const create_cell_t *create_cell,
  650. int relayed)
  651. {
  652. cell_t cell;
  653. circid_t id;
  654. int r;
  655. tor_assert(circ);
  656. tor_assert(circ->n_chan);
  657. tor_assert(create_cell);
  658. tor_assert(create_cell->cell_type == CELL_CREATE ||
  659. create_cell->cell_type == CELL_CREATE_FAST ||
  660. create_cell->cell_type == CELL_CREATE2);
  661. id = get_unique_circ_id_by_chan(circ->n_chan);
  662. if (!id) {
  663. static ratelim_t circid_warning_limit = RATELIM_INIT(9600);
  664. log_fn_ratelim(&circid_warning_limit, LOG_WARN, LD_CIRC,
  665. "failed to get unique circID.");
  666. goto error;
  667. }
  668. memset(&cell, 0, sizeof(cell_t));
  669. r = relayed ? create_cell_format_relayed(&cell, create_cell)
  670. : create_cell_format(&cell, create_cell);
  671. if (r < 0) {
  672. log_warn(LD_CIRC,"Couldn't format create cell");
  673. goto error;
  674. }
  675. log_debug(LD_CIRC,"Chosen circID %u.", (unsigned)id);
  676. circuit_set_n_circid_chan(circ, id, circ->n_chan);
  677. cell.circ_id = circ->n_circ_id;
  678. append_cell_to_circuit_queue(circ, circ->n_chan, &cell,
  679. CELL_DIRECTION_OUT, 0);
  680. if (CIRCUIT_IS_ORIGIN(circ)) {
  681. /* Update began timestamp for circuits starting their first hop */
  682. if (TO_ORIGIN_CIRCUIT(circ)->cpath->state == CPATH_STATE_CLOSED) {
  683. if (!CHANNEL_IS_OPEN(circ->n_chan)) {
  684. log_warn(LD_CIRC,
  685. "Got first hop for a circuit without an opened channel. "
  686. "State: %s.", channel_state_to_string(circ->n_chan->state));
  687. tor_fragile_assert();
  688. }
  689. tor_gettimeofday(&circ->timestamp_began);
  690. }
  691. /* mark it so it gets better rate limiting treatment. */
  692. channel_timestamp_client(circ->n_chan);
  693. }
  694. return 0;
  695. error:
  696. circ->n_chan = NULL;
  697. return -1;
  698. }
  699. /** We've decided to start our reachability testing. If all
  700. * is set, log this to the user. Return 1 if we did, or 0 if
  701. * we chose not to log anything. */
  702. int
  703. inform_testing_reachability(void)
  704. {
  705. char dirbuf[128];
  706. char *address;
  707. const routerinfo_t *me = router_get_my_routerinfo();
  708. if (!me)
  709. return 0;
  710. address = tor_dup_ip(me->addr);
  711. control_event_server_status(LOG_NOTICE,
  712. "CHECKING_REACHABILITY ORADDRESS=%s:%d",
  713. address, me->or_port);
  714. if (me->dir_port) {
  715. tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d",
  716. address, me->dir_port);
  717. control_event_server_status(LOG_NOTICE,
  718. "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
  719. address, me->dir_port);
  720. }
  721. log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
  722. "(this may take up to %d minutes -- look for log "
  723. "messages indicating success)",
  724. address, me->or_port,
  725. me->dir_port ? dirbuf : "",
  726. me->dir_port ? "are" : "is",
  727. TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT/60);
  728. tor_free(address);
  729. return 1;
  730. }
  731. /** Return true iff we should send a create_fast cell to start building a given
  732. * circuit */
  733. static inline int
  734. should_use_create_fast_for_circuit(origin_circuit_t *circ)
  735. {
  736. const or_options_t *options = get_options();
  737. tor_assert(circ->cpath);
  738. tor_assert(circ->cpath->extend_info);
  739. if (!circuit_has_usable_onion_key(circ)) {
  740. /* We don't have ntor, and we don't have or can't use TAP,
  741. * so our hand is forced: only a create_fast will work. */
  742. return 1;
  743. }
  744. if (public_server_mode(options)) {
  745. /* We're a server, and we have a usable onion key. We can choose.
  746. * Prefer to blend our circuit into the other circuits we are
  747. * creating on behalf of others. */
  748. return 0;
  749. }
  750. return networkstatus_get_param(NULL, "usecreatefast", 0, 0, 1);
  751. }
  752. /**
  753. * Return true if <b>circ</b> is the type of circuit we want to count
  754. * timeouts from.
  755. *
  756. * In particular, we want to consider any circuit that plans to build
  757. * at least 3 hops (but maybe more), but has 3 or fewer hops built
  758. * so far.
  759. *
  760. * We still want to consider circuits before 3 hops, because we need
  761. * to decide if we should convert them to a measurement circuit in
  762. * circuit_build_times_handle_completed_hop(), rather than letting
  763. * slow circuits get killed right away.
  764. */
  765. int
  766. circuit_timeout_want_to_count_circ(const origin_circuit_t *circ)
  767. {
  768. return !circ->has_opened
  769. && circ->build_state->desired_path_len >= DEFAULT_ROUTE_LEN
  770. && circuit_get_cpath_opened_len(circ) <= DEFAULT_ROUTE_LEN;
  771. }
  772. /** Decide whether to use a TAP or ntor handshake for connecting to <b>ei</b>
  773. * directly, and set *<b>cell_type_out</b> and *<b>handshake_type_out</b>
  774. * accordingly.
  775. * Note that TAP handshakes in CREATE cells are only used for direct
  776. * connections:
  777. * - from Tor2web to intro points not in the client's consensus, and
  778. * - from Single Onions to rend points not in the service's consensus.
  779. * This is checked in onion_populate_cpath. */
  780. static void
  781. circuit_pick_create_handshake(uint8_t *cell_type_out,
  782. uint16_t *handshake_type_out,
  783. const extend_info_t *ei)
  784. {
  785. /* torspec says: In general, clients SHOULD use CREATE whenever they are
  786. * using the TAP handshake, and CREATE2 otherwise. */
  787. if (extend_info_supports_ntor(ei)) {
  788. *cell_type_out = CELL_CREATE2;
  789. *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR;
  790. } else {
  791. /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
  792. *cell_type_out = CELL_CREATE;
  793. *handshake_type_out = ONION_HANDSHAKE_TYPE_TAP;
  794. }
  795. }
  796. /** Decide whether to use a TAP or ntor handshake for extending to <b>ei</b>
  797. * and set *<b>handshake_type_out</b> accordingly. Decide whether we should
  798. * use an EXTEND2 or an EXTEND cell to do so, and set *<b>cell_type_out</b>
  799. * and *<b>create_cell_type_out</b> accordingly.
  800. * Note that TAP handshakes in EXTEND cells are only used:
  801. * - from clients to intro points, and
  802. * - from hidden services to rend points.
  803. * This is checked in onion_populate_cpath.
  804. */
  805. static void
  806. circuit_pick_extend_handshake(uint8_t *cell_type_out,
  807. uint8_t *create_cell_type_out,
  808. uint16_t *handshake_type_out,
  809. const extend_info_t *ei)
  810. {
  811. uint8_t t;
  812. circuit_pick_create_handshake(&t, handshake_type_out, ei);
  813. /* torspec says: Clients SHOULD use the EXTEND format whenever sending a TAP
  814. * handshake... In other cases, clients SHOULD use EXTEND2. */
  815. if (*handshake_type_out != ONION_HANDSHAKE_TYPE_TAP) {
  816. *cell_type_out = RELAY_COMMAND_EXTEND2;
  817. *create_cell_type_out = CELL_CREATE2;
  818. } else {
  819. /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
  820. *cell_type_out = RELAY_COMMAND_EXTEND;
  821. *create_cell_type_out = CELL_CREATE;
  822. }
  823. }
  824. /**
  825. * Return true iff <b>purpose</b> is a purpose for a circuit which is
  826. * allowed to have no guard configured, even if the circuit is multihop
  827. * and guards are enabled.
  828. */
  829. static int
  830. circuit_purpose_may_omit_guard(int purpose)
  831. {
  832. switch (purpose) {
  833. case CIRCUIT_PURPOSE_TESTING:
  834. case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
  835. /* Testing circuits may omit guards because they're measuring
  836. * liveness or performance, and don't want guards to interfere. */
  837. return 1;
  838. default:
  839. /* All other multihop circuits should use guards if guards are
  840. * enabled. */
  841. return 0;
  842. }
  843. }
  844. /** This is the backbone function for building circuits.
  845. *
  846. * If circ's first hop is closed, then we need to build a create
  847. * cell and send it forward.
  848. *
  849. * Otherwise, if circ's cpath still has any non-open hops, we need to
  850. * build a relay extend cell and send it forward to the next non-open hop.
  851. *
  852. * If all hops on the cpath are open, we're done building the circuit
  853. * and we should do housekeeping for the newly opened circuit.
  854. *
  855. * Return -reason if we want to tear down circ, else return 0.
  856. */
  857. int
  858. circuit_send_next_onion_skin(origin_circuit_t *circ)
  859. {
  860. tor_assert(circ);
  861. if (circ->cpath->state == CPATH_STATE_CLOSED) {
  862. /* Case one: we're on the first hop. */
  863. return circuit_send_first_onion_skin(circ);
  864. }
  865. tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
  866. tor_assert(circ->base_.state == CIRCUIT_STATE_BUILDING);
  867. crypt_path_t *hop = onion_next_hop_in_cpath(circ->cpath);
  868. circuit_build_times_handle_completed_hop(circ);
  869. if (hop) {
  870. /* Case two: we're on a hop after the first. */
  871. return circuit_send_intermediate_onion_skin(circ, hop);
  872. }
  873. /* Case three: the circuit is finished. Do housekeeping tasks on it. */
  874. return circuit_build_no_more_hops(circ);
  875. }
  876. /**
  877. * Called from circuit_send_next_onion_skin() when we find ourselves connected
  878. * to the first hop in <b>circ</b>: Send a CREATE or CREATE2 or CREATE_FAST
  879. * cell to that hop. Return 0 on success; -reason on failure (if the circuit
  880. * should be torn down).
  881. */
  882. static int
  883. circuit_send_first_onion_skin(origin_circuit_t *circ)
  884. {
  885. int fast;
  886. int len;
  887. const node_t *node;
  888. create_cell_t cc;
  889. memset(&cc, 0, sizeof(cc));
  890. log_debug(LD_CIRC,"First skin; sending create cell.");
  891. if (circ->build_state->onehop_tunnel) {
  892. control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
  893. } else {
  894. control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);
  895. /* If this is not a one-hop tunnel, the channel is being used
  896. * for traffic that wants anonymity and protection from traffic
  897. * analysis (such as netflow record retention). That means we want
  898. * to pad it.
  899. */
  900. if (circ->base_.n_chan->channel_usage < CHANNEL_USED_FOR_FULL_CIRCS)
  901. circ->base_.n_chan->channel_usage = CHANNEL_USED_FOR_FULL_CIRCS;
  902. }
  903. node = node_get_by_id(circ->base_.n_chan->identity_digest);
  904. fast = should_use_create_fast_for_circuit(circ);
  905. if (!fast) {
  906. /* We know the right onion key: we should send a create cell. */
  907. circuit_pick_create_handshake(&cc.cell_type, &cc.handshake_type,
  908. circ->cpath->extend_info);
  909. } else {
  910. /* We don't know an onion key, so we need to fall back to CREATE_FAST. */
  911. cc.cell_type = CELL_CREATE_FAST;
  912. cc.handshake_type = ONION_HANDSHAKE_TYPE_FAST;
  913. }
  914. len = onion_skin_create(cc.handshake_type,
  915. circ->cpath->extend_info,
  916. &circ->cpath->handshake_state,
  917. cc.onionskin);
  918. if (len < 0) {
  919. log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
  920. return - END_CIRC_REASON_INTERNAL;
  921. }
  922. cc.handshake_len = len;
  923. if (circuit_deliver_create_cell(TO_CIRCUIT(circ), &cc, 0) < 0)
  924. return - END_CIRC_REASON_RESOURCELIMIT;
  925. circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
  926. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  927. log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'",
  928. fast ? "CREATE_FAST" : "CREATE",
  929. node ? node_describe(node) : "<unnamed>");
  930. return 0;
  931. }
  932. /**
  933. * Called from circuit_send_next_onion_skin() when we find that we have no
  934. * more hops: mark the circuit as finished, and perform the necessary
  935. * bookkeeping. Return 0 on success; -reason on failure (if the circuit
  936. * should be torn down).
  937. */
  938. static int
  939. circuit_build_no_more_hops(origin_circuit_t *circ)
  940. {
  941. guard_usable_t r;
  942. if (! circ->guard_state) {
  943. if (circuit_get_cpath_len(circ) != 1 &&
  944. ! circuit_purpose_may_omit_guard(circ->base_.purpose) &&
  945. get_options()->UseEntryGuards) {
  946. log_warn(LD_BUG, "%d-hop circuit %p with purpose %d has no "
  947. "guard state",
  948. circuit_get_cpath_len(circ), circ, circ->base_.purpose);
  949. }
  950. r = GUARD_USABLE_NOW;
  951. } else {
  952. r = entry_guard_succeeded(&circ->guard_state);
  953. }
  954. const int is_usable_for_streams = (r == GUARD_USABLE_NOW);
  955. if (r == GUARD_USABLE_NOW) {
  956. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  957. } else if (r == GUARD_MAYBE_USABLE_LATER) {
  958. // Wait till either a better guard succeeds, or till
  959. // all better guards fail.
  960. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_GUARD_WAIT);
  961. } else {
  962. tor_assert_nonfatal(r == GUARD_USABLE_NEVER);
  963. return - END_CIRC_REASON_INTERNAL;
  964. }
  965. /* XXXX #21422 -- the rest of this branch needs careful thought!
  966. * Some of the things here need to happen when a circuit becomes
  967. * mechanically open; some need to happen when it is actually usable.
  968. * I think I got them right, but more checking would be wise. -NM
  969. */
  970. log_info(LD_CIRC,"circuit built!");
  971. circuit_reset_failure_count(0);
  972. if (circ->build_state->onehop_tunnel || circ->has_opened) {
  973. control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0);
  974. }
  975. pathbias_count_build_success(circ);
  976. circuit_rep_hist_note_result(circ);
  977. if (is_usable_for_streams)
  978. circuit_has_opened(circ); /* do other actions as necessary */
  979. if (!have_completed_a_circuit() && !circ->build_state->onehop_tunnel) {
  980. const or_options_t *options = get_options();
  981. note_that_we_completed_a_circuit();
  982. /* FFFF Log a count of known routers here */
  983. log_notice(LD_GENERAL,
  984. "Tor has successfully opened a circuit. "
  985. "Looks like client functionality is working.");
  986. if (control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0) == 0) {
  987. log_notice(LD_GENERAL,
  988. "Tor has successfully opened a circuit. "
  989. "Looks like client functionality is working.");
  990. }
  991. control_event_client_status(LOG_NOTICE, "CIRCUIT_ESTABLISHED");
  992. clear_broken_connection_map(1);
  993. if (server_mode(options) && !check_whether_orport_reachable(options)) {
  994. inform_testing_reachability();
  995. consider_testing_reachability(1, 1);
  996. }
  997. }
  998. /* We're done with measurement circuits here. Just close them */
  999. if (circ->base_.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
  1000. circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
  1001. }
  1002. return 0;
  1003. }
  1004. /**
  1005. * Called from circuit_send_next_onion_skin() when we find that we have a hop
  1006. * other than the first that we need to extend to: use <b>hop</b>'s
  1007. * information to extend the circuit another step. Return 0 on success;
  1008. * -reason on failure (if the circuit should be torn down).
  1009. */
  1010. static int
  1011. circuit_send_intermediate_onion_skin(origin_circuit_t *circ,
  1012. crypt_path_t *hop)
  1013. {
  1014. int len;
  1015. extend_cell_t ec;
  1016. memset(&ec, 0, sizeof(ec));
  1017. log_debug(LD_CIRC,"starting to send subsequent skin.");
  1018. if (tor_addr_family(&hop->extend_info->addr) != AF_INET) {
  1019. log_warn(LD_BUG, "Trying to extend to a non-IPv4 address.");
  1020. return - END_CIRC_REASON_INTERNAL;
  1021. }
  1022. circuit_pick_extend_handshake(&ec.cell_type,
  1023. &ec.create_cell.cell_type,
  1024. &ec.create_cell.handshake_type,
  1025. hop->extend_info);
  1026. tor_addr_copy(&ec.orport_ipv4.addr, &hop->extend_info->addr);
  1027. ec.orport_ipv4.port = hop->extend_info->port;
  1028. tor_addr_make_unspec(&ec.orport_ipv6.addr);
  1029. memcpy(ec.node_id, hop->extend_info->identity_digest, DIGEST_LEN);
  1030. /* Set the ED25519 identity too -- it will only get included
  1031. * in the extend2 cell if we're configured to use it, though. */
  1032. ed25519_pubkey_copy(&ec.ed_pubkey, &hop->extend_info->ed_identity);
  1033. len = onion_skin_create(ec.create_cell.handshake_type,
  1034. hop->extend_info,
  1035. &hop->handshake_state,
  1036. ec.create_cell.onionskin);
  1037. if (len < 0) {
  1038. log_warn(LD_CIRC,"onion_skin_create failed.");
  1039. return - END_CIRC_REASON_INTERNAL;
  1040. }
  1041. ec.create_cell.handshake_len = len;
  1042. log_info(LD_CIRC,"Sending extend relay cell.");
  1043. {
  1044. uint8_t command = 0;
  1045. uint16_t payload_len=0;
  1046. uint8_t payload[RELAY_PAYLOAD_SIZE];
  1047. if (extend_cell_format(&command, &payload_len, payload, &ec)<0) {
  1048. log_warn(LD_CIRC,"Couldn't format extend cell");
  1049. return -END_CIRC_REASON_INTERNAL;
  1050. }
  1051. /* send it to hop->prev, because that relay will transfer
  1052. * it to a create cell and then send to hop */
  1053. if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
  1054. command,
  1055. (char*)payload, payload_len,
  1056. hop->prev) < 0)
  1057. return 0; /* circuit is closed */
  1058. }
  1059. hop->state = CPATH_STATE_AWAITING_KEYS;
  1060. return 0;
  1061. }
  1062. /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
  1063. * something has also gone wrong with our network: notify the user,
  1064. * and abandon all not-yet-used circuits. */
  1065. void
  1066. circuit_note_clock_jumped(int seconds_elapsed)
  1067. {
  1068. int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE;
  1069. tor_log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; "
  1070. "assuming established circuits no longer work.",
  1071. seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed,
  1072. seconds_elapsed >=0 ? "forward" : "backward");
  1073. control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%d",
  1074. seconds_elapsed);
  1075. /* so we log when it works again */
  1076. note_that_we_maybe_cant_complete_circuits();
  1077. control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
  1078. "CLOCK_JUMPED");
  1079. circuit_mark_all_unused_circs();
  1080. circuit_mark_all_dirty_circs_as_unusable();
  1081. if (seconds_elapsed < 0) {
  1082. /* Restart all the timers in case we jumped a long way into the past. */
  1083. reset_all_main_loop_timers();
  1084. }
  1085. }
  1086. /** Take the 'extend' <b>cell</b>, pull out addr/port plus the onion
  1087. * skin and identity digest for the next hop. If we're already connected,
  1088. * pass the onion skin to the next hop using a create cell; otherwise
  1089. * launch a new OR connection, and <b>circ</b> will notice when the
  1090. * connection succeeds or fails.
  1091. *
  1092. * Return -1 if we want to warn and tear down the circuit, else return 0.
  1093. */
  1094. int
  1095. circuit_extend(cell_t *cell, circuit_t *circ)
  1096. {
  1097. channel_t *n_chan;
  1098. relay_header_t rh;
  1099. extend_cell_t ec;
  1100. const char *msg = NULL;
  1101. int should_launch = 0;
  1102. if (circ->n_chan) {
  1103. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1104. "n_chan already set. Bug/attack. Closing.");
  1105. return -1;
  1106. }
  1107. if (circ->n_hop) {
  1108. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1109. "conn to next hop already launched. Bug/attack. Closing.");
  1110. return -1;
  1111. }
  1112. if (!server_mode(get_options())) {
  1113. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1114. "Got an extend cell, but running as a client. Closing.");
  1115. return -1;
  1116. }
  1117. relay_header_unpack(&rh, cell->payload);
  1118. if (extend_cell_parse(&ec, rh.command,
  1119. cell->payload+RELAY_HEADER_SIZE,
  1120. rh.length) < 0) {
  1121. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1122. "Can't parse extend cell. Closing circuit.");
  1123. return -1;
  1124. }
  1125. if (!ec.orport_ipv4.port || tor_addr_is_null(&ec.orport_ipv4.addr)) {
  1126. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1127. "Client asked me to extend to zero destination port or addr.");
  1128. return -1;
  1129. }
  1130. if (tor_addr_is_internal(&ec.orport_ipv4.addr, 0) &&
  1131. !get_options()->ExtendAllowPrivateAddresses) {
  1132. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1133. "Client asked me to extend to a private address");
  1134. return -1;
  1135. }
  1136. /* Check if they asked us for 0000..0000. We support using
  1137. * an empty fingerprint for the first hop (e.g. for a bridge relay),
  1138. * but we don't want to let clients send us extend cells for empty
  1139. * fingerprints -- a) because it opens the user up to a mitm attack,
  1140. * and b) because it lets an attacker force the relay to hold open a
  1141. * new TLS connection for each extend request. */
  1142. if (tor_digest_is_zero((const char*)ec.node_id)) {
  1143. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1144. "Client asked me to extend without specifying an id_digest.");
  1145. return -1;
  1146. }
  1147. /* Fill in ed_pubkey if it was not provided and we can infer it from
  1148. * our networkstatus */
  1149. if (ed25519_public_key_is_zero(&ec.ed_pubkey)) {
  1150. const node_t *node = node_get_by_id((const char*)ec.node_id);
  1151. const ed25519_public_key_t *node_ed_id = NULL;
  1152. if (node &&
  1153. node_supports_ed25519_link_authentication(node, 1) &&
  1154. (node_ed_id = node_get_ed25519_id(node))) {
  1155. ed25519_pubkey_copy(&ec.ed_pubkey, node_ed_id);
  1156. }
  1157. }
  1158. /* Next, check if we're being asked to connect to the hop that the
  1159. * extend cell came from. There isn't any reason for that, and it can
  1160. * assist circular-path attacks. */
  1161. if (tor_memeq(ec.node_id,
  1162. TO_OR_CIRCUIT(circ)->p_chan->identity_digest,
  1163. DIGEST_LEN)) {
  1164. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1165. "Client asked me to extend back to the previous hop.");
  1166. return -1;
  1167. }
  1168. /* Check the previous hop Ed25519 ID too */
  1169. if (! ed25519_public_key_is_zero(&ec.ed_pubkey) &&
  1170. ed25519_pubkey_eq(&ec.ed_pubkey,
  1171. &TO_OR_CIRCUIT(circ)->p_chan->ed25519_identity)) {
  1172. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  1173. "Client asked me to extend back to the previous hop "
  1174. "(by Ed25519 ID).");
  1175. }
  1176. n_chan = channel_get_for_extend((const char*)ec.node_id,
  1177. &ec.ed_pubkey,
  1178. &ec.orport_ipv4.addr,
  1179. &msg,
  1180. &should_launch);
  1181. if (!n_chan) {
  1182. log_debug(LD_CIRC|LD_OR,"Next router (%s): %s",
  1183. fmt_addrport(&ec.orport_ipv4.addr,ec.orport_ipv4.port),
  1184. msg?msg:"????");
  1185. circ->n_hop = extend_info_new(NULL /*nickname*/,
  1186. (const char*)ec.node_id,
  1187. &ec.ed_pubkey,
  1188. NULL, /*onion_key*/
  1189. NULL, /*curve25519_key*/
  1190. &ec.orport_ipv4.addr,
  1191. ec.orport_ipv4.port);
  1192. circ->n_chan_create_cell = tor_memdup(&ec.create_cell,
  1193. sizeof(ec.create_cell));
  1194. circuit_set_state(circ, CIRCUIT_STATE_CHAN_WAIT);
  1195. if (should_launch) {
  1196. /* we should try to open a connection */
  1197. n_chan = channel_connect_for_circuit(&ec.orport_ipv4.addr,
  1198. ec.orport_ipv4.port,
  1199. (const char*)ec.node_id,
  1200. &ec.ed_pubkey);
  1201. if (!n_chan) {
  1202. log_info(LD_CIRC,"Launching n_chan failed. Closing circuit.");
  1203. circuit_mark_for_close(circ, END_CIRC_REASON_CONNECTFAILED);
  1204. return 0;
  1205. }
  1206. log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
  1207. }
  1208. /* return success. The onion/circuit/etc will be taken care of
  1209. * automatically (may already have been) whenever n_chan reaches
  1210. * OR_CONN_STATE_OPEN.
  1211. */
  1212. return 0;
  1213. }
  1214. tor_assert(!circ->n_hop); /* Connection is already established. */
  1215. circ->n_chan = n_chan;
  1216. log_debug(LD_CIRC,
  1217. "n_chan is %s",
  1218. channel_get_canonical_remote_descr(n_chan));
  1219. if (circuit_deliver_create_cell(circ, &ec.create_cell, 1) < 0)
  1220. return -1;
  1221. return 0;
  1222. }
  1223. /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in key_data.
  1224. *
  1225. * If <b>is_hs_v3</b> is set, this cpath will be used for next gen hidden
  1226. * service circuits and <b>key_data</b> must be at least
  1227. * HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN bytes in length.
  1228. *
  1229. * If <b>is_hs_v3</b> is not set, key_data must contain CPATH_KEY_MATERIAL_LEN
  1230. * bytes, which are used as follows:
  1231. * - 20 to initialize f_digest
  1232. * - 20 to initialize b_digest
  1233. * - 16 to key f_crypto
  1234. * - 16 to key b_crypto
  1235. *
  1236. * (If 'reverse' is true, then f_XX and b_XX are swapped.)
  1237. *
  1238. * Return 0 if init was successful, else -1 if it failed.
  1239. */
  1240. int
  1241. circuit_init_cpath_crypto(crypt_path_t *cpath,
  1242. const char *key_data, size_t key_data_len,
  1243. int reverse, int is_hs_v3)
  1244. {
  1245. crypto_digest_t *tmp_digest;
  1246. crypto_cipher_t *tmp_crypto;
  1247. size_t digest_len = 0;
  1248. size_t cipher_key_len = 0;
  1249. tor_assert(cpath);
  1250. tor_assert(key_data);
  1251. tor_assert(!(cpath->f_crypto || cpath->b_crypto ||
  1252. cpath->f_digest || cpath->b_digest));
  1253. /* Basic key size validation */
  1254. if (is_hs_v3 && BUG(key_data_len != HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN)) {
  1255. return -1;
  1256. } else if (!is_hs_v3 && BUG(key_data_len != CPATH_KEY_MATERIAL_LEN)) {
  1257. return -1;
  1258. }
  1259. /* If we are using this cpath for next gen onion services use SHA3-256,
  1260. otherwise use good ol' SHA1 */
  1261. if (is_hs_v3) {
  1262. digest_len = DIGEST256_LEN;
  1263. cipher_key_len = CIPHER256_KEY_LEN;
  1264. cpath->f_digest = crypto_digest256_new(DIGEST_SHA3_256);
  1265. cpath->b_digest = crypto_digest256_new(DIGEST_SHA3_256);
  1266. } else {
  1267. digest_len = DIGEST_LEN;
  1268. cipher_key_len = CIPHER_KEY_LEN;
  1269. cpath->f_digest = crypto_digest_new();
  1270. cpath->b_digest = crypto_digest_new();
  1271. }
  1272. tor_assert(digest_len != 0);
  1273. tor_assert(cipher_key_len != 0);
  1274. const int cipher_key_bits = (int) cipher_key_len * 8;
  1275. crypto_digest_add_bytes(cpath->f_digest, key_data, digest_len);
  1276. crypto_digest_add_bytes(cpath->b_digest, key_data+digest_len, digest_len);
  1277. cpath->f_crypto = crypto_cipher_new_with_bits(key_data+(2*digest_len),
  1278. cipher_key_bits);
  1279. if (!cpath->f_crypto) {
  1280. log_warn(LD_BUG,"Forward cipher initialization failed.");
  1281. return -1;
  1282. }
  1283. cpath->b_crypto = crypto_cipher_new_with_bits(
  1284. key_data+(2*digest_len)+cipher_key_len,
  1285. cipher_key_bits);
  1286. if (!cpath->b_crypto) {
  1287. log_warn(LD_BUG,"Backward cipher initialization failed.");
  1288. return -1;
  1289. }
  1290. if (reverse) {
  1291. tmp_digest = cpath->f_digest;
  1292. cpath->f_digest = cpath->b_digest;
  1293. cpath->b_digest = tmp_digest;
  1294. tmp_crypto = cpath->f_crypto;
  1295. cpath->f_crypto = cpath->b_crypto;
  1296. cpath->b_crypto = tmp_crypto;
  1297. }
  1298. return 0;
  1299. }
  1300. /** A "created" cell <b>reply</b> came back to us on circuit <b>circ</b>.
  1301. * (The body of <b>reply</b> varies depending on what sort of handshake
  1302. * this is.)
  1303. *
  1304. * Calculate the appropriate keys and digests, make sure KH is
  1305. * correct, and initialize this hop of the cpath.
  1306. *
  1307. * Return - reason if we want to mark circ for close, else return 0.
  1308. */
  1309. int
  1310. circuit_finish_handshake(origin_circuit_t *circ,
  1311. const created_cell_t *reply)
  1312. {
  1313. char keys[CPATH_KEY_MATERIAL_LEN];
  1314. crypt_path_t *hop;
  1315. int rv;
  1316. if ((rv = pathbias_count_build_attempt(circ)) < 0) {
  1317. log_warn(LD_CIRC, "pathbias_count_build_attempt failed: %d", rv);
  1318. return rv;
  1319. }
  1320. if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) {
  1321. hop = circ->cpath;
  1322. } else {
  1323. hop = onion_next_hop_in_cpath(circ->cpath);
  1324. if (!hop) { /* got an extended when we're all done? */
  1325. log_warn(LD_PROTOCOL,"got extended when circ already built? Closing.");
  1326. return - END_CIRC_REASON_TORPROTOCOL;
  1327. }
  1328. }
  1329. tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);
  1330. {
  1331. const char *msg = NULL;
  1332. if (onion_skin_client_handshake(hop->handshake_state.tag,
  1333. &hop->handshake_state,
  1334. reply->reply, reply->handshake_len,
  1335. (uint8_t*)keys, sizeof(keys),
  1336. (uint8_t*)hop->rend_circ_nonce,
  1337. &msg) < 0) {
  1338. if (msg)
  1339. log_warn(LD_CIRC,"onion_skin_client_handshake failed: %s", msg);
  1340. return -END_CIRC_REASON_TORPROTOCOL;
  1341. }
  1342. }
  1343. onion_handshake_state_release(&hop->handshake_state);
  1344. if (circuit_init_cpath_crypto(hop, keys, sizeof(keys), 0, 0)<0) {
  1345. return -END_CIRC_REASON_TORPROTOCOL;
  1346. }
  1347. hop->state = CPATH_STATE_OPEN;
  1348. log_info(LD_CIRC,"Finished building circuit hop:");
  1349. circuit_log_path(LOG_INFO,LD_CIRC,circ);
  1350. control_event_circuit_status(circ, CIRC_EVENT_EXTENDED, 0);
  1351. return 0;
  1352. }
  1353. /** We received a relay truncated cell on circ.
  1354. *
  1355. * Since we don't send truncates currently, getting a truncated
  1356. * means that a connection broke or an extend failed. For now,
  1357. * just give up: force circ to close, and return 0.
  1358. */
  1359. int
  1360. circuit_truncated(origin_circuit_t *circ, crypt_path_t *layer, int reason)
  1361. {
  1362. // crypt_path_t *victim;
  1363. // connection_t *stream;
  1364. tor_assert(circ);
  1365. tor_assert(layer);
  1366. /* XXX Since we don't send truncates currently, getting a truncated
  1367. * means that a connection broke or an extend failed. For now,
  1368. * just give up.
  1369. */
  1370. circuit_mark_for_close(TO_CIRCUIT(circ),
  1371. END_CIRC_REASON_FLAG_REMOTE|reason);
  1372. return 0;
  1373. #if 0
  1374. while (layer->next != circ->cpath) {
  1375. /* we need to clear out layer->next */
  1376. victim = layer->next;
  1377. log_debug(LD_CIRC, "Killing a layer of the cpath.");
  1378. for (stream = circ->p_streams; stream; stream=stream->next_stream) {
  1379. if (stream->cpath_layer == victim) {
  1380. log_info(LD_APP, "Marking stream %d for close because of truncate.",
  1381. stream->stream_id);
  1382. /* no need to send 'end' relay cells,
  1383. * because the other side's already dead
  1384. */
  1385. connection_mark_unattached_ap(stream, END_STREAM_REASON_DESTROY);
  1386. }
  1387. }
  1388. layer->next = victim->next;
  1389. circuit_free_cpath_node(victim);
  1390. }
  1391. log_info(LD_CIRC, "finished");
  1392. return 0;
  1393. #endif /* 0 */
  1394. }
  1395. /** Given a response payload and keys, initialize, then send a created
  1396. * cell back.
  1397. */
  1398. int
  1399. onionskin_answer(or_circuit_t *circ,
  1400. const created_cell_t *created_cell,
  1401. const char *keys, size_t keys_len,
  1402. const uint8_t *rend_circ_nonce)
  1403. {
  1404. cell_t cell;
  1405. crypt_path_t *tmp_cpath;
  1406. tor_assert(keys_len == CPATH_KEY_MATERIAL_LEN);
  1407. if (created_cell_format(&cell, created_cell) < 0) {
  1408. log_warn(LD_BUG,"couldn't format created cell (type=%d, len=%d)",
  1409. (int)created_cell->cell_type, (int)created_cell->handshake_len);
  1410. return -1;
  1411. }
  1412. cell.circ_id = circ->p_circ_id;
  1413. tmp_cpath = tor_malloc_zero(sizeof(crypt_path_t));
  1414. tmp_cpath->magic = CRYPT_PATH_MAGIC;
  1415. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  1416. log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.",
  1417. (unsigned int)get_uint32(keys),
  1418. (unsigned int)get_uint32(keys+20));
  1419. if (circuit_init_cpath_crypto(tmp_cpath, keys, keys_len, 0, 0)<0) {
  1420. log_warn(LD_BUG,"Circuit initialization failed");
  1421. tor_free(tmp_cpath);
  1422. return -1;
  1423. }
  1424. circ->n_digest = tmp_cpath->f_digest;
  1425. circ->n_crypto = tmp_cpath->f_crypto;
  1426. circ->p_digest = tmp_cpath->b_digest;
  1427. circ->p_crypto = tmp_cpath->b_crypto;
  1428. tmp_cpath->magic = 0;
  1429. tor_free(tmp_cpath);
  1430. memcpy(circ->rend_circ_nonce, rend_circ_nonce, DIGEST_LEN);
  1431. int used_create_fast = (created_cell->cell_type == CELL_CREATED_FAST);
  1432. append_cell_to_circuit_queue(TO_CIRCUIT(circ),
  1433. circ->p_chan, &cell, CELL_DIRECTION_IN, 0);
  1434. log_debug(LD_CIRC,"Finished sending '%s' cell.",
  1435. used_create_fast ? "created_fast" : "created");
  1436. /* Ignore the local bit when ExtendAllowPrivateAddresses is set:
  1437. * it violates the assumption that private addresses are local.
  1438. * Also, many test networks run on local addresses, and
  1439. * TestingTorNetwork sets ExtendAllowPrivateAddresses. */
  1440. if ((!channel_is_local(circ->p_chan)
  1441. || get_options()->ExtendAllowPrivateAddresses)
  1442. && !channel_is_outgoing(circ->p_chan)) {
  1443. /* record that we could process create cells from a non-local conn
  1444. * that we didn't initiate; presumably this means that create cells
  1445. * can reach us too. */
  1446. router_orport_found_reachable();
  1447. }
  1448. return 0;
  1449. }
  1450. /** Helper for new_route_len(). Choose a circuit length for purpose
  1451. * <b>purpose</b>: DEFAULT_ROUTE_LEN (+ 1 if someone else chose the
  1452. * exit). If someone else chose the exit, they could be colluding
  1453. * with the exit, so add a randomly selected node to preserve
  1454. * anonymity.
  1455. *
  1456. * Here, "exit node" sometimes means an OR acting as an internal
  1457. * endpoint, rather than as a relay to an external endpoint. This
  1458. * means there need to be at least DEFAULT_ROUTE_LEN routers between
  1459. * us and the internal endpoint to preserve the same anonymity
  1460. * properties that we would get when connecting to an external
  1461. * endpoint. These internal endpoints can include:
  1462. *
  1463. * - Connections to a directory of hidden services
  1464. * (CIRCUIT_PURPOSE_C_GENERAL)
  1465. *
  1466. * - A client connecting to an introduction point, which the hidden
  1467. * service picked (CIRCUIT_PURPOSE_C_INTRODUCING, via
  1468. * circuit_get_open_circ_or_launch() which rewrites it from
  1469. * CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT)
  1470. *
  1471. * - A hidden service connecting to a rendezvous point, which the
  1472. * client picked (CIRCUIT_PURPOSE_S_CONNECT_REND, via
  1473. * rend_service_receive_introduction() and
  1474. * rend_service_relaunch_rendezvous)
  1475. *
  1476. * There are currently two situations where we picked the exit node
  1477. * ourselves, making DEFAULT_ROUTE_LEN a safe circuit length:
  1478. *
  1479. * - We are a hidden service connecting to an introduction point
  1480. * (CIRCUIT_PURPOSE_S_ESTABLISH_INTRO, via
  1481. * rend_service_launch_establish_intro())
  1482. *
  1483. * - We are a router testing its own reachabiity
  1484. * (CIRCUIT_PURPOSE_TESTING, via consider_testing_reachability())
  1485. *
  1486. * onion_pick_cpath_exit() bypasses us (by not calling
  1487. * new_route_len()) in the one-hop tunnel case, so we don't need to
  1488. * handle that.
  1489. */
  1490. int
  1491. route_len_for_purpose(uint8_t purpose, extend_info_t *exit_ei)
  1492. {
  1493. int routelen = DEFAULT_ROUTE_LEN;
  1494. int known_purpose = 0;
  1495. if (circuit_should_use_vanguards(purpose)) {
  1496. /* Clients want an extra hop for rends to avoid linkability.
  1497. * Services want it for intro points to avoid publishing their
  1498. * layer3 guards. They want it for hsdir posts to use
  1499. * their full layer3 guard set for those connections.
  1500. * Ex: C - G - L2 - L3 - R
  1501. * S - G - L2 - L3 - HSDIR
  1502. * S - G - L2 - L3 - I
  1503. */
  1504. if (purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND ||
  1505. purpose == CIRCUIT_PURPOSE_S_HSDIR_POST ||
  1506. purpose == CIRCUIT_PURPOSE_HS_VANGUARDS ||
  1507. purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
  1508. return routelen+1;
  1509. /* If we only have Layer2 vanguards, then we do not need
  1510. * the extra hop for linkabilty reasons (see below).
  1511. * This means all hops can be of the form:
  1512. * S/C - G - L2 - M - R/HSDir/I
  1513. */
  1514. if (get_options()->HSLayer2Nodes && !get_options()->HSLayer3Nodes)
  1515. return routelen+1;
  1516. /* For connections to hsdirs, clients want two extra hops
  1517. * when using layer3 guards, to avoid linkability.
  1518. * Same goes for intro points. Note that the route len
  1519. * includes the intro point or hsdir, hence the +2.
  1520. * Ex: C - G - L2 - L3 - M - I
  1521. * C - G - L2 - L3 - M - HSDIR
  1522. * S - G - L2 - L3 - M - R
  1523. */
  1524. if (purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
  1525. purpose == CIRCUIT_PURPOSE_C_HSDIR_GET ||
  1526. purpose == CIRCUIT_PURPOSE_C_INTRODUCING)
  1527. return routelen+2;
  1528. }
  1529. if (!exit_ei)
  1530. return routelen;
  1531. switch (purpose) {
  1532. /* These two purposes connect to a router that we chose, so
  1533. * DEFAULT_ROUTE_LEN is safe. */
  1534. case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
  1535. /* hidden service connecting to introduction point */
  1536. case CIRCUIT_PURPOSE_TESTING:
  1537. /* router reachability testing */
  1538. known_purpose = 1;
  1539. break;
  1540. /* These three purposes connect to a router that someone else
  1541. * might have chosen, so add an extra hop to protect anonymity. */
  1542. case CIRCUIT_PURPOSE_C_GENERAL:
  1543. case CIRCUIT_PURPOSE_C_HSDIR_GET:
  1544. case CIRCUIT_PURPOSE_S_HSDIR_POST:
  1545. /* connecting to hidden service directory */
  1546. case CIRCUIT_PURPOSE_C_INTRODUCING:
  1547. /* client connecting to introduction point */
  1548. case CIRCUIT_PURPOSE_S_CONNECT_REND:
  1549. /* hidden service connecting to rendezvous point */
  1550. known_purpose = 1;
  1551. routelen++;
  1552. break;
  1553. default:
  1554. /* Got a purpose not listed above along with a chosen exit.
  1555. * Increase the circuit length by one anyway for safety. */
  1556. routelen++;
  1557. break;
  1558. }
  1559. if (BUG(exit_ei && !known_purpose)) {
  1560. log_warn(LD_BUG, "Unhandled purpose %d with a chosen exit; "
  1561. "assuming routelen %d.", purpose, routelen);
  1562. }
  1563. return routelen;
  1564. }
  1565. /** Choose a length for a circuit of purpose <b>purpose</b> and check
  1566. * if enough routers are available.
  1567. *
  1568. * If the routerlist <b>nodes</b> doesn't have enough routers
  1569. * to handle the desired path length, return -1.
  1570. */
  1571. STATIC int
  1572. new_route_len(uint8_t purpose, extend_info_t *exit_ei, smartlist_t *nodes)
  1573. {
  1574. int num_acceptable_routers;
  1575. int routelen;
  1576. tor_assert(nodes);
  1577. routelen = route_len_for_purpose(purpose, exit_ei);
  1578. num_acceptable_routers = count_acceptable_nodes(nodes);
  1579. log_debug(LD_CIRC,"Chosen route length %d (%d/%d routers suitable).",
  1580. routelen, num_acceptable_routers, smartlist_len(nodes));
  1581. if (num_acceptable_routers < routelen) {
  1582. log_info(LD_CIRC,
  1583. "Not enough acceptable routers (%d/%d). Discarding this circuit.",
  1584. num_acceptable_routers, routelen);
  1585. return -1;
  1586. }
  1587. return routelen;
  1588. }
  1589. /** Return a newly allocated list of uint16_t * for each predicted port not
  1590. * handled by a current circuit. */
  1591. static smartlist_t *
  1592. circuit_get_unhandled_ports(time_t now)
  1593. {
  1594. smartlist_t *dest = rep_hist_get_predicted_ports(now);
  1595. circuit_remove_handled_ports(dest);
  1596. return dest;
  1597. }
  1598. /** Return 1 if we already have circuits present or on the way for
  1599. * all anticipated ports. Return 0 if we should make more.
  1600. *
  1601. * If we're returning 0, set need_uptime and need_capacity to
  1602. * indicate any requirements that the unhandled ports have.
  1603. */
  1604. MOCK_IMPL(int,
  1605. circuit_all_predicted_ports_handled, (time_t now, int *need_uptime,
  1606. int *need_capacity))
  1607. {
  1608. int i, enough;
  1609. uint16_t *port;
  1610. smartlist_t *sl = circuit_get_unhandled_ports(now);
  1611. smartlist_t *LongLivedServices = get_options()->LongLivedPorts;
  1612. tor_assert(need_uptime);
  1613. tor_assert(need_capacity);
  1614. // Always predict need_capacity
  1615. *need_capacity = 1;
  1616. enough = (smartlist_len(sl) == 0);
  1617. for (i = 0; i < smartlist_len(sl); ++i) {
  1618. port = smartlist_get(sl, i);
  1619. if (smartlist_contains_int_as_string(LongLivedServices, *port))
  1620. *need_uptime = 1;
  1621. tor_free(port);
  1622. }
  1623. smartlist_free(sl);
  1624. return enough;
  1625. }
  1626. /** Return 1 if <b>node</b> can handle one or more of the ports in
  1627. * <b>needed_ports</b>, else return 0.
  1628. */
  1629. static int
  1630. node_handles_some_port(const node_t *node, smartlist_t *needed_ports)
  1631. { /* XXXX MOVE */
  1632. int i;
  1633. uint16_t port;
  1634. for (i = 0; i < smartlist_len(needed_ports); ++i) {
  1635. addr_policy_result_t r;
  1636. /* alignment issues aren't a worry for this dereference, since
  1637. needed_ports is explicitly a smartlist of uint16_t's */
  1638. port = *(uint16_t *)smartlist_get(needed_ports, i);
  1639. tor_assert(port);
  1640. if (node)
  1641. r = compare_tor_addr_to_node_policy(NULL, port, node);
  1642. else
  1643. continue;
  1644. if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
  1645. return 1;
  1646. }
  1647. return 0;
  1648. }
  1649. /** Return true iff <b>conn</b> needs another general circuit to be
  1650. * built. */
  1651. static int
  1652. ap_stream_wants_exit_attention(connection_t *conn)
  1653. {
  1654. entry_connection_t *entry;
  1655. if (conn->type != CONN_TYPE_AP)
  1656. return 0;
  1657. entry = TO_ENTRY_CONN(conn);
  1658. if (conn->state == AP_CONN_STATE_CIRCUIT_WAIT &&
  1659. !conn->marked_for_close &&
  1660. !(entry->want_onehop) && /* ignore one-hop streams */
  1661. !(entry->use_begindir) && /* ignore targeted dir fetches */
  1662. !(entry->chosen_exit_name) && /* ignore defined streams */
  1663. !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn)) &&
  1664. !circuit_stream_is_being_handled(TO_ENTRY_CONN(conn), 0,
  1665. MIN_CIRCUITS_HANDLING_STREAM))
  1666. return 1;
  1667. return 0;
  1668. }
  1669. /** Return a pointer to a suitable router to be the exit node for the
  1670. * general-purpose circuit we're about to build.
  1671. *
  1672. * Look through the connection array, and choose a router that maximizes
  1673. * the number of pending streams that can exit from this router.
  1674. *
  1675. * Return NULL if we can't find any suitable routers.
  1676. */
  1677. static const node_t *
  1678. choose_good_exit_server_general(int need_uptime, int need_capacity)
  1679. {
  1680. int *n_supported;
  1681. int n_pending_connections = 0;
  1682. smartlist_t *connections;
  1683. int best_support = -1;
  1684. int n_best_support=0;
  1685. const or_options_t *options = get_options();
  1686. const smartlist_t *the_nodes;
  1687. const node_t *selected_node=NULL;
  1688. connections = get_connection_array();
  1689. /* Count how many connections are waiting for a circuit to be built.
  1690. * We use this for log messages now, but in the future we may depend on it.
  1691. */
  1692. SMARTLIST_FOREACH(connections, connection_t *, conn,
  1693. {
  1694. if (ap_stream_wants_exit_attention(conn))
  1695. ++n_pending_connections;
  1696. });
  1697. // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
  1698. // n_pending_connections);
  1699. /* Now we count, for each of the routers in the directory, how many
  1700. * of the pending connections could possibly exit from that
  1701. * router (n_supported[i]). (We can't be sure about cases where we
  1702. * don't know the IP address of the pending connection.)
  1703. *
  1704. * -1 means "Don't use this router at all."
  1705. */
  1706. the_nodes = nodelist_get_list();
  1707. n_supported = tor_calloc(smartlist_len(the_nodes), sizeof(int));
  1708. SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
  1709. const int i = node_sl_idx;
  1710. if (router_digest_is_me(node->identity)) {
  1711. n_supported[i] = -1;
  1712. // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
  1713. /* XXX there's probably a reverse predecessor attack here, but
  1714. * it's slow. should we take this out? -RD
  1715. */
  1716. continue;
  1717. }
  1718. if (!node_has_descriptor(node)) {
  1719. n_supported[i] = -1;
  1720. continue;
  1721. }
  1722. if (!node->is_running || node->is_bad_exit) {
  1723. n_supported[i] = -1;
  1724. continue; /* skip routers that are known to be down or bad exits */
  1725. }
  1726. if (node_get_purpose(node) != ROUTER_PURPOSE_GENERAL) {
  1727. /* never pick a non-general node as a random exit. */
  1728. n_supported[i] = -1;
  1729. continue;
  1730. }
  1731. if (routerset_contains_node(options->ExcludeExitNodesUnion_, node)) {
  1732. n_supported[i] = -1;
  1733. continue; /* user asked us not to use it, no matter what */
  1734. }
  1735. if (options->ExitNodes &&
  1736. !routerset_contains_node(options->ExitNodes, node)) {
  1737. n_supported[i] = -1;
  1738. continue; /* not one of our chosen exit nodes */
  1739. }
  1740. if (node_is_unreliable(node, need_uptime, need_capacity, 0)) {
  1741. n_supported[i] = -1;
  1742. continue; /* skip routers that are not suitable. Don't worry if
  1743. * this makes us reject all the possible routers: if so,
  1744. * we'll retry later in this function with need_update and
  1745. * need_capacity set to 0. */
  1746. }
  1747. if (!(node->is_valid)) {
  1748. /* if it's invalid and we don't want it */
  1749. n_supported[i] = -1;
  1750. // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
  1751. // router->nickname, i);
  1752. continue; /* skip invalid routers */
  1753. }
  1754. /* We do not allow relays that allow single hop exits by default. Option
  1755. * was deprecated in 0.2.9.2-alpha and removed in 0.3.1.0-alpha. */
  1756. if (node_allows_single_hop_exits(node)) {
  1757. n_supported[i] = -1;
  1758. continue;
  1759. }
  1760. if (node_exit_policy_rejects_all(node)) {
  1761. n_supported[i] = -1;
  1762. // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
  1763. // router->nickname, i);
  1764. continue; /* skip routers that reject all */
  1765. }
  1766. n_supported[i] = 0;
  1767. /* iterate over connections */
  1768. SMARTLIST_FOREACH_BEGIN(connections, connection_t *, conn) {
  1769. if (!ap_stream_wants_exit_attention(conn))
  1770. continue; /* Skip everything but APs in CIRCUIT_WAIT */
  1771. if (connection_ap_can_use_exit(TO_ENTRY_CONN(conn), node)) {
  1772. ++n_supported[i];
  1773. // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
  1774. // router->nickname, i, n_supported[i]);
  1775. } else {
  1776. // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
  1777. // router->nickname, i);
  1778. }
  1779. } SMARTLIST_FOREACH_END(conn);
  1780. if (n_pending_connections > 0 && n_supported[i] == 0) {
  1781. /* Leave best_support at -1 if that's where it is, so we can
  1782. * distinguish it later. */
  1783. continue;
  1784. }
  1785. if (n_supported[i] > best_support) {
  1786. /* If this router is better than previous ones, remember its index
  1787. * and goodness, and start counting how many routers are this good. */
  1788. best_support = n_supported[i]; n_best_support=1;
  1789. // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
  1790. // router->nickname);
  1791. } else if (n_supported[i] == best_support) {
  1792. /* If this router is _as good_ as the best one, just increment the
  1793. * count of equally good routers.*/
  1794. ++n_best_support;
  1795. }
  1796. } SMARTLIST_FOREACH_END(node);
  1797. log_info(LD_CIRC,
  1798. "Found %d servers that might support %d/%d pending connections.",
  1799. n_best_support, best_support >= 0 ? best_support : 0,
  1800. n_pending_connections);
  1801. /* If any routers definitely support any pending connections, choose one
  1802. * at random. */
  1803. if (best_support > 0) {
  1804. smartlist_t *supporting = smartlist_new();
  1805. SMARTLIST_FOREACH(the_nodes, const node_t *, node, {
  1806. if (n_supported[node_sl_idx] == best_support)
  1807. smartlist_add(supporting, (void*)node);
  1808. });
  1809. selected_node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
  1810. smartlist_free(supporting);
  1811. } else {
  1812. /* Either there are no pending connections, or no routers even seem to
  1813. * possibly support any of them. Choose a router at random that satisfies
  1814. * at least one predicted exit port. */
  1815. int attempt;
  1816. smartlist_t *needed_ports, *supporting;
  1817. if (best_support == -1) {
  1818. if (need_uptime || need_capacity) {
  1819. log_info(LD_CIRC,
  1820. "We couldn't find any live%s%s routers; falling back "
  1821. "to list of all routers.",
  1822. need_capacity?", fast":"",
  1823. need_uptime?", stable":"");
  1824. tor_free(n_supported);
  1825. return choose_good_exit_server_general(0, 0);
  1826. }
  1827. log_notice(LD_CIRC, "All routers are down or won't exit%s -- "
  1828. "choosing a doomed exit at random.",
  1829. options->ExcludeExitNodesUnion_ ? " or are Excluded" : "");
  1830. }
  1831. supporting = smartlist_new();
  1832. needed_ports = circuit_get_unhandled_ports(time(NULL));
  1833. for (attempt = 0; attempt < 2; attempt++) {
  1834. /* try once to pick only from routers that satisfy a needed port,
  1835. * then if there are none, pick from any that support exiting. */
  1836. SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
  1837. if (n_supported[node_sl_idx] != -1 &&
  1838. (attempt || node_handles_some_port(node, needed_ports))) {
  1839. // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
  1840. // try, router->nickname);
  1841. smartlist_add(supporting, (void*)node);
  1842. }
  1843. } SMARTLIST_FOREACH_END(node);
  1844. selected_node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
  1845. if (selected_node)
  1846. break;
  1847. smartlist_clear(supporting);
  1848. /* If we reach this point, we can't actually support any unhandled
  1849. * predicted ports, so clear all the remaining ones. */
  1850. if (smartlist_len(needed_ports))
  1851. rep_hist_remove_predicted_ports(needed_ports);
  1852. }
  1853. SMARTLIST_FOREACH(needed_ports, uint16_t *, cp, tor_free(cp));
  1854. smartlist_free(needed_ports);
  1855. smartlist_free(supporting);
  1856. }
  1857. tor_free(n_supported);
  1858. if (selected_node) {
  1859. log_info(LD_CIRC, "Chose exit server '%s'", node_describe(selected_node));
  1860. return selected_node;
  1861. }
  1862. if (options->ExitNodes) {
  1863. log_warn(LD_CIRC,
  1864. "No exits in ExitNodes%s seem to be running: "
  1865. "can't choose an exit.",
  1866. options->ExcludeExitNodesUnion_ ?
  1867. ", except possibly those excluded by your configuration, " : "");
  1868. }
  1869. return NULL;
  1870. }
  1871. #if defined(ENABLE_TOR2WEB_MODE) || defined(TOR_UNIT_TESTS)
  1872. /* The config option Tor2webRendezvousPoints has been set and we need
  1873. * to pick an RP out of that set. Make sure that the RP we choose is
  1874. * alive, and return it. Return NULL if no usable RP could be found in
  1875. * Tor2webRendezvousPoints. */
  1876. STATIC const node_t *
  1877. pick_tor2web_rendezvous_node(router_crn_flags_t flags,
  1878. const or_options_t *options)
  1879. {
  1880. const node_t *rp_node = NULL;
  1881. const int need_desc = (flags & CRN_NEED_DESC) != 0;
  1882. const int pref_addr = (flags & CRN_PREF_ADDR) != 0;
  1883. const int direct_conn = (flags & CRN_DIRECT_CONN) != 0;
  1884. smartlist_t *whitelisted_live_rps = smartlist_new();
  1885. smartlist_t *all_live_nodes = smartlist_new();
  1886. tor_assert(options->Tor2webRendezvousPoints);
  1887. /* Add all running nodes to all_live_nodes */
  1888. router_add_running_nodes_to_smartlist(all_live_nodes,
  1889. 0, 0, 0,
  1890. need_desc,
  1891. pref_addr,
  1892. direct_conn);
  1893. /* Filter all_live_nodes to only add live *and* whitelisted RPs to
  1894. * the list whitelisted_live_rps. */
  1895. SMARTLIST_FOREACH_BEGIN(all_live_nodes, node_t *, live_node) {
  1896. if (routerset_contains_node(options->Tor2webRendezvousPoints, live_node)) {
  1897. smartlist_add(whitelisted_live_rps, live_node);
  1898. }
  1899. } SMARTLIST_FOREACH_END(live_node);
  1900. /* Honor ExcludeNodes */
  1901. if (options->ExcludeNodes) {
  1902. routerset_subtract_nodes(whitelisted_live_rps, options->ExcludeNodes);
  1903. }
  1904. /* Now pick randomly amongst the whitelisted RPs. No need to waste time
  1905. doing bandwidth load balancing, for most use cases
  1906. 'whitelisted_live_rps' contains a single OR anyway. */
  1907. rp_node = smartlist_choose(whitelisted_live_rps);
  1908. if (!rp_node) {
  1909. log_warn(LD_REND, "Could not find a Rendezvous Point that suits "
  1910. "the purposes of Tor2webRendezvousPoints. Choosing random one.");
  1911. }
  1912. smartlist_free(whitelisted_live_rps);
  1913. smartlist_free(all_live_nodes);
  1914. return rp_node;
  1915. }
  1916. #endif /* defined(ENABLE_TOR2WEB_MODE) || defined(TOR_UNIT_TESTS) */
  1917. /* Pick a Rendezvous Point for our HS circuits according to <b>flags</b>. */
  1918. static const node_t *
  1919. pick_rendezvous_node(router_crn_flags_t flags)
  1920. {
  1921. const or_options_t *options = get_options();
  1922. #ifdef ENABLE_TOR2WEB_MODE
  1923. /* We want to connect directly to the node if we can */
  1924. router_crn_flags_t direct_flags = flags;
  1925. direct_flags |= CRN_PREF_ADDR;
  1926. direct_flags |= CRN_DIRECT_CONN;
  1927. /* The user wants us to pick specific RPs. */
  1928. if (options->Tor2webRendezvousPoints) {
  1929. const node_t *tor2web_rp = pick_tor2web_rendezvous_node(direct_flags,
  1930. options);
  1931. if (tor2web_rp) {
  1932. return tor2web_rp;
  1933. }
  1934. }
  1935. /* Else, if no direct, preferred tor2web RP was found, fall back to choosing
  1936. * a random direct node */
  1937. const node_t *node = router_choose_random_node(NULL, options->ExcludeNodes,
  1938. direct_flags);
  1939. /* Return the direct node (if found), or log a message and fall back to an
  1940. * indirect connection. */
  1941. if (node) {
  1942. return node;
  1943. } else {
  1944. log_info(LD_REND,
  1945. "Unable to find a random rendezvous point that is reachable via "
  1946. "a direct connection, falling back to a 3-hop path.");
  1947. }
  1948. #endif /* defined(ENABLE_TOR2WEB_MODE) */
  1949. return router_choose_random_node(NULL, options->ExcludeNodes, flags);
  1950. }
  1951. /*
  1952. * Helper function to pick a configured restricted middle node
  1953. * (either HSLayer2Nodes or HSLayer3Nodes).
  1954. *
  1955. * Make sure that the node we chose is alive, and not excluded,
  1956. * and return it.
  1957. *
  1958. * The exclude_set is a routerset of nodes that the selected node
  1959. * must not match, and the exclude_list is a simple list of nodes
  1960. * that the selected node must not be in. Either or both may be
  1961. * NULL.
  1962. *
  1963. * Return NULL if no usable nodes could be found. */
  1964. static const node_t *
  1965. pick_restricted_middle_node(router_crn_flags_t flags,
  1966. const routerset_t *pick_from,
  1967. const routerset_t *exclude_set,
  1968. const smartlist_t *exclude_list,
  1969. int position_hint)
  1970. {
  1971. const node_t *middle_node = NULL;
  1972. smartlist_t *whitelisted_live_middles = smartlist_new();
  1973. smartlist_t *all_live_nodes = smartlist_new();
  1974. tor_assert(pick_from);
  1975. /* Add all running nodes to all_live_nodes */
  1976. router_add_running_nodes_to_smartlist(all_live_nodes,
  1977. (flags & CRN_NEED_UPTIME) != 0,
  1978. (flags & CRN_NEED_CAPACITY) != 0,
  1979. (flags & CRN_NEED_GUARD) != 0,
  1980. (flags & CRN_NEED_DESC) != 0,
  1981. (flags & CRN_PREF_ADDR) != 0,
  1982. (flags & CRN_DIRECT_CONN) != 0);
  1983. /* Filter all_live_nodes to only add live *and* whitelisted middles
  1984. * to the list whitelisted_live_middles. */
  1985. SMARTLIST_FOREACH_BEGIN(all_live_nodes, node_t *, live_node) {
  1986. if (routerset_contains_node(pick_from, live_node)) {
  1987. smartlist_add(whitelisted_live_middles, live_node);
  1988. }
  1989. } SMARTLIST_FOREACH_END(live_node);
  1990. /* Honor ExcludeNodes */
  1991. if (exclude_set) {
  1992. routerset_subtract_nodes(whitelisted_live_middles, exclude_set);
  1993. }
  1994. if (exclude_list) {
  1995. smartlist_subtract(whitelisted_live_middles, exclude_list);
  1996. }
  1997. /**
  1998. * Max number of restricted nodes before we alert the user and try
  1999. * to load balance for them.
  2000. *
  2001. * The most aggressive vanguard design had 16 nodes at layer3.
  2002. * Let's give a small ceiling above that. */
  2003. #define MAX_SANE_RESTRICTED_NODES 20
  2004. /* If the user (or associated tor controller) selected only a few nodes,
  2005. * assume they took load balancing into account and don't do it for them.
  2006. *
  2007. * If there are a lot of nodes in here, assume they did not load balance
  2008. * and do it for them, but also warn them that they may be Doing It Wrong.
  2009. */
  2010. if (smartlist_len(whitelisted_live_middles) <=
  2011. MAX_SANE_RESTRICTED_NODES) {
  2012. middle_node = smartlist_choose(whitelisted_live_middles);
  2013. } else {
  2014. static ratelim_t pinned_notice_limit = RATELIM_INIT(24*3600);
  2015. log_fn_ratelim(&pinned_notice_limit, LOG_NOTICE, LD_CIRC,
  2016. "Your _HSLayer%dNodes setting has resulted "
  2017. "in %d total nodes. This is a lot of nodes. "
  2018. "You may want to consider using a Tor controller "
  2019. "to select and update a smaller set of nodes instead.",
  2020. position_hint, smartlist_len(whitelisted_live_middles));
  2021. /* NO_WEIGHTING here just means don't take node flags into account
  2022. * (ie: use consensus measurement only). This is done so that
  2023. * we don't further surprise the user by not using Exits that they
  2024. * specified at all */
  2025. middle_node = node_sl_choose_by_bandwidth(whitelisted_live_middles,
  2026. NO_WEIGHTING);
  2027. }
  2028. smartlist_free(whitelisted_live_middles);
  2029. smartlist_free(all_live_nodes);
  2030. return middle_node;
  2031. }
  2032. /** Return a pointer to a suitable router to be the exit node for the
  2033. * circuit of purpose <b>purpose</b> that we're about to build (or NULL
  2034. * if no router is suitable).
  2035. *
  2036. * For general-purpose circuits, pass it off to
  2037. * choose_good_exit_server_general()
  2038. *
  2039. * For client-side rendezvous circuits, choose a random node, weighted
  2040. * toward the preferences in 'options'.
  2041. */
  2042. static const node_t *
  2043. choose_good_exit_server(origin_circuit_t *circ, int need_uptime,
  2044. int need_capacity, int is_internal, int need_hs_v3)
  2045. {
  2046. const or_options_t *options = get_options();
  2047. router_crn_flags_t flags = CRN_NEED_DESC;
  2048. if (need_uptime)
  2049. flags |= CRN_NEED_UPTIME;
  2050. if (need_capacity)
  2051. flags |= CRN_NEED_CAPACITY;
  2052. if (need_hs_v3)
  2053. flags |= CRN_RENDEZVOUS_V3;
  2054. switch (TO_CIRCUIT(circ)->purpose) {
  2055. case CIRCUIT_PURPOSE_C_HSDIR_GET:
  2056. case CIRCUIT_PURPOSE_S_HSDIR_POST:
  2057. case CIRCUIT_PURPOSE_HS_VANGUARDS:
  2058. /* For these three, we want to pick the exit like a middle hop,
  2059. * since it should be random. */
  2060. tor_assert_nonfatal(is_internal);
  2061. /* Falls through */
  2062. case CIRCUIT_PURPOSE_C_GENERAL:
  2063. if (is_internal) /* pick it like a middle hop */
  2064. return router_choose_random_node(NULL, options->ExcludeNodes, flags);
  2065. else
  2066. return choose_good_exit_server_general(need_uptime,need_capacity);
  2067. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  2068. {
  2069. /* Pick a new RP */
  2070. const node_t *rendezvous_node = pick_rendezvous_node(flags);
  2071. log_info(LD_REND, "Picked new RP: %s",
  2072. safe_str_client(node_describe(rendezvous_node)));
  2073. return rendezvous_node;
  2074. }
  2075. }
  2076. log_warn(LD_BUG,"Unhandled purpose %d", TO_CIRCUIT(circ)->purpose);
  2077. tor_fragile_assert();
  2078. return NULL;
  2079. }
  2080. /** Log a warning if the user specified an exit for the circuit that
  2081. * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
  2082. static void
  2083. warn_if_last_router_excluded(origin_circuit_t *circ,
  2084. const extend_info_t *exit_ei)
  2085. {
  2086. const or_options_t *options = get_options();
  2087. routerset_t *rs = options->ExcludeNodes;
  2088. const char *description;
  2089. uint8_t purpose = circ->base_.purpose;
  2090. if (circ->build_state->onehop_tunnel)
  2091. return;
  2092. switch (purpose)
  2093. {
  2094. default:
  2095. case CIRCUIT_PURPOSE_OR:
  2096. case CIRCUIT_PURPOSE_INTRO_POINT:
  2097. case CIRCUIT_PURPOSE_REND_POINT_WAITING:
  2098. case CIRCUIT_PURPOSE_REND_ESTABLISHED:
  2099. log_warn(LD_BUG, "Called on non-origin circuit (purpose %d, %s)",
  2100. (int)purpose,
  2101. circuit_purpose_to_string(purpose));
  2102. return;
  2103. case CIRCUIT_PURPOSE_S_HSDIR_POST:
  2104. case CIRCUIT_PURPOSE_C_HSDIR_GET:
  2105. case CIRCUIT_PURPOSE_C_GENERAL:
  2106. if (circ->build_state->is_internal)
  2107. return;
  2108. description = "requested exit node";
  2109. rs = options->ExcludeExitNodesUnion_;
  2110. break;
  2111. case CIRCUIT_PURPOSE_C_INTRODUCING:
  2112. case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
  2113. case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
  2114. case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
  2115. case CIRCUIT_PURPOSE_S_CONNECT_REND:
  2116. case CIRCUIT_PURPOSE_S_REND_JOINED:
  2117. case CIRCUIT_PURPOSE_TESTING:
  2118. return;
  2119. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  2120. case CIRCUIT_PURPOSE_C_REND_READY:
  2121. case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
  2122. case CIRCUIT_PURPOSE_C_REND_JOINED:
  2123. description = "chosen rendezvous point";
  2124. break;
  2125. case CIRCUIT_PURPOSE_CONTROLLER:
  2126. rs = options->ExcludeExitNodesUnion_;
  2127. description = "controller-selected circuit target";
  2128. break;
  2129. }
  2130. if (routerset_contains_extendinfo(rs, exit_ei)) {
  2131. /* We should never get here if StrictNodes is set to 1. */
  2132. if (options->StrictNodes) {
  2133. log_warn(LD_BUG, "Using %s '%s' which is listed in ExcludeNodes%s, "
  2134. "even though StrictNodes is set. Please report. "
  2135. "(Circuit purpose: %s)",
  2136. description, extend_info_describe(exit_ei),
  2137. rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
  2138. circuit_purpose_to_string(purpose));
  2139. } else {
  2140. log_warn(LD_CIRC, "Using %s '%s' which is listed in "
  2141. "ExcludeNodes%s, because no better options were available. To "
  2142. "prevent this (and possibly break your Tor functionality), "
  2143. "set the StrictNodes configuration option. "
  2144. "(Circuit purpose: %s)",
  2145. description, extend_info_describe(exit_ei),
  2146. rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
  2147. circuit_purpose_to_string(purpose));
  2148. }
  2149. circuit_log_path(LOG_WARN, LD_CIRC, circ);
  2150. }
  2151. return;
  2152. }
  2153. /** Decide a suitable length for circ's cpath, and pick an exit
  2154. * router (or use <b>exit</b> if provided). Store these in the
  2155. * cpath.
  2156. *
  2157. * If <b>is_hs_v3_rp_circuit</b> is set, then this exit should be suitable to
  2158. * be used as an HS v3 rendezvous point.
  2159. *
  2160. * Return 0 if ok, -1 if circuit should be closed. */
  2161. static int
  2162. onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit_ei,
  2163. int is_hs_v3_rp_circuit)
  2164. {
  2165. cpath_build_state_t *state = circ->build_state;
  2166. if (state->onehop_tunnel) {
  2167. log_debug(LD_CIRC, "Launching a one-hop circuit for dir tunnel%s.",
  2168. (rend_allow_non_anonymous_connection(get_options()) ?
  2169. ", or intro or rendezvous connection" : ""));
  2170. state->desired_path_len = 1;
  2171. } else {
  2172. int r = new_route_len(circ->base_.purpose, exit_ei, nodelist_get_list());
  2173. if (r < 1) /* must be at least 1 */
  2174. return -1;
  2175. state->desired_path_len = r;
  2176. }
  2177. if (exit_ei) { /* the circuit-builder pre-requested one */
  2178. warn_if_last_router_excluded(circ, exit_ei);
  2179. log_info(LD_CIRC,"Using requested exit node '%s'",
  2180. extend_info_describe(exit_ei));
  2181. exit_ei = extend_info_dup(exit_ei);
  2182. } else { /* we have to decide one */
  2183. const node_t *node =
  2184. choose_good_exit_server(circ, state->need_uptime,
  2185. state->need_capacity, state->is_internal,
  2186. is_hs_v3_rp_circuit);
  2187. if (!node) {
  2188. log_warn(LD_CIRC,"Failed to choose an exit server");
  2189. return -1;
  2190. }
  2191. exit_ei = extend_info_from_node(node, 0);
  2192. if (BUG(exit_ei == NULL))
  2193. return -1;
  2194. }
  2195. state->chosen_exit = exit_ei;
  2196. return 0;
  2197. }
  2198. /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
  2199. * hop to the cpath reflecting this. Don't send the next extend cell --
  2200. * the caller will do this if it wants to.
  2201. */
  2202. int
  2203. circuit_append_new_exit(origin_circuit_t *circ, extend_info_t *exit_ei)
  2204. {
  2205. cpath_build_state_t *state;
  2206. tor_assert(exit_ei);
  2207. tor_assert(circ);
  2208. state = circ->build_state;
  2209. tor_assert(state);
  2210. extend_info_free(state->chosen_exit);
  2211. state->chosen_exit = extend_info_dup(exit_ei);
  2212. ++circ->build_state->desired_path_len;
  2213. onion_append_hop(&circ->cpath, exit_ei);
  2214. return 0;
  2215. }
  2216. /** Take an open <b>circ</b>, and add a new hop at the end, based on
  2217. * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
  2218. * send the next extend cell to begin connecting to that hop.
  2219. */
  2220. int
  2221. circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit_ei)
  2222. {
  2223. int err_reason = 0;
  2224. warn_if_last_router_excluded(circ, exit_ei);
  2225. tor_gettimeofday(&circ->base_.timestamp_began);
  2226. circuit_append_new_exit(circ, exit_ei);
  2227. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  2228. if ((err_reason = circuit_send_next_onion_skin(circ))<0) {
  2229. log_warn(LD_CIRC, "Couldn't extend circuit to new point %s.",
  2230. extend_info_describe(exit_ei));
  2231. circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
  2232. return -1;
  2233. }
  2234. // XXX: Should cannibalized circuits be dirty or not? Not easy to say..
  2235. return 0;
  2236. }
  2237. /** Return the number of routers in <b>routers</b> that are currently up
  2238. * and available for building circuits through.
  2239. */
  2240. MOCK_IMPL(STATIC int,
  2241. count_acceptable_nodes, (smartlist_t *nodes))
  2242. {
  2243. int num=0;
  2244. SMARTLIST_FOREACH_BEGIN(nodes, const node_t *, node) {
  2245. // log_debug(LD_CIRC,
  2246. // "Contemplating whether router %d (%s) is a new option.",
  2247. // i, r->nickname);
  2248. if (! node->is_running)
  2249. // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
  2250. continue;
  2251. if (! node->is_valid)
  2252. // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
  2253. continue;
  2254. if (! node_has_descriptor(node))
  2255. continue;
  2256. /* The node has a descriptor, so we can just check the ntor key directly */
  2257. if (!node_has_curve25519_onion_key(node))
  2258. continue;
  2259. ++num;
  2260. } SMARTLIST_FOREACH_END(node);
  2261. // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
  2262. return num;
  2263. }
  2264. /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
  2265. * This function is used to extend cpath by another hop.
  2266. */
  2267. void
  2268. onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop)
  2269. {
  2270. if (*head_ptr) {
  2271. new_hop->next = (*head_ptr);
  2272. new_hop->prev = (*head_ptr)->prev;
  2273. (*head_ptr)->prev->next = new_hop;
  2274. (*head_ptr)->prev = new_hop;
  2275. } else {
  2276. *head_ptr = new_hop;
  2277. new_hop->prev = new_hop->next = new_hop;
  2278. }
  2279. }
  2280. #ifdef TOR_UNIT_TESTS
  2281. /** Unittest helper function: Count number of hops in cpath linked list. */
  2282. unsigned int
  2283. cpath_get_n_hops(crypt_path_t **head_ptr)
  2284. {
  2285. unsigned int n_hops = 0;
  2286. crypt_path_t *tmp;
  2287. if (!*head_ptr) {
  2288. return 0;
  2289. }
  2290. tmp = *head_ptr;
  2291. do {
  2292. n_hops++;
  2293. tmp = tmp->next;
  2294. } while (tmp != *head_ptr);
  2295. return n_hops;
  2296. }
  2297. #endif /* defined(TOR_UNIT_TESTS) */
  2298. /**
  2299. * Build a list of nodes to exclude from the choice of this middle
  2300. * hop, based on already chosen nodes.
  2301. *
  2302. * XXX: At present, this function does not exclude any nodes from
  2303. * the vanguard circuits. See
  2304. * https://trac.torproject.org/projects/tor/ticket/24487
  2305. */
  2306. static smartlist_t *
  2307. build_middle_exclude_list(uint8_t purpose,
  2308. cpath_build_state_t *state,
  2309. crypt_path_t *head,
  2310. int cur_len)
  2311. {
  2312. smartlist_t *excluded;
  2313. const node_t *r;
  2314. crypt_path_t *cpath;
  2315. int i;
  2316. excluded = smartlist_new();
  2317. /* Add the exit to the exclude list (note that the exit/last hop is always
  2318. * chosen first in circuit_establish_circuit()). */
  2319. if ((r = build_state_get_exit_node(state))) {
  2320. nodelist_add_node_and_family(excluded, r);
  2321. }
  2322. /* XXX: We don't apply any other previously selected node restrictions for
  2323. * vanguards, and allow nodes to be reused for those hop positions in the
  2324. * same circuit. This is because after many rotations, you get to learn
  2325. * inner guard nodes through the nodes that are not selected for outer
  2326. * hops.
  2327. *
  2328. * The alternative is building the circuit in reverse. Reverse calls to
  2329. * onion_extend_cpath() (ie: select outer hops first) would then have the
  2330. * property that you don't gain information about inner hops by observing
  2331. * outer ones. See https://trac.torproject.org/projects/tor/ticket/24487
  2332. * for this.
  2333. *
  2334. * (Note further that we can and do still exclude the exit in the block
  2335. * above, because it is chosen first in circuit_establish_circuit()..) */
  2336. if (circuit_should_use_vanguards(purpose)) {
  2337. return excluded;
  2338. }
  2339. for (i = 0, cpath = head; cpath && i < cur_len; ++i, cpath=cpath->next) {
  2340. if ((r = node_get_by_id(cpath->extend_info->identity_digest))) {
  2341. nodelist_add_node_and_family(excluded, r);
  2342. }
  2343. }
  2344. return excluded;
  2345. }
  2346. /** Return true if we MUST use vanguards for picking this middle node. */
  2347. static int
  2348. middle_node_must_be_vanguard(const or_options_t *options,
  2349. uint8_t purpose, int cur_len)
  2350. {
  2351. /* If this is not a hidden service circuit, don't use vanguards */
  2352. if (!circuit_purpose_is_hidden_service(purpose)) {
  2353. return 0;
  2354. }
  2355. /* If we have sticky L2 nodes, and this is an L2 pick, use vanguards */
  2356. if (options->HSLayer2Nodes && cur_len == 1) {
  2357. return 1;
  2358. }
  2359. /* If we have sticky L3 nodes, and this is an L3 pick, use vanguards */
  2360. if (options->HSLayer3Nodes && cur_len == 2) {
  2361. return 1;
  2362. }
  2363. return 0;
  2364. }
  2365. /** Pick a sticky vanguard middle node or return NULL if not found.
  2366. * See doc of pick_restricted_middle_node() for argument details. */
  2367. static const node_t *
  2368. pick_vanguard_middle_node(const or_options_t *options,
  2369. router_crn_flags_t flags, int cur_len,
  2370. const smartlist_t *excluded)
  2371. {
  2372. const routerset_t *vanguard_routerset = NULL;
  2373. const node_t *node = NULL;
  2374. /* Pick the right routerset based on the current hop */
  2375. if (cur_len == 1) {
  2376. vanguard_routerset = options->HSLayer2Nodes;
  2377. } else if (cur_len == 2) {
  2378. vanguard_routerset = options->HSLayer3Nodes;
  2379. } else {
  2380. /* guaranteed by middle_node_should_be_vanguard() */
  2381. tor_assert_nonfatal_unreached();
  2382. return NULL;
  2383. }
  2384. node = pick_restricted_middle_node(flags, vanguard_routerset,
  2385. options->ExcludeNodes, excluded,
  2386. cur_len+1);
  2387. if (!node) {
  2388. static ratelim_t pinned_warning_limit = RATELIM_INIT(300);
  2389. log_fn_ratelim(&pinned_warning_limit, LOG_WARN, LD_CIRC,
  2390. "Could not find a node that matches the configured "
  2391. "_HSLayer%dNodes set", cur_len+1);
  2392. }
  2393. return node;
  2394. }
  2395. /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
  2396. * and <b>state</b> and the cpath <b>head</b> (currently populated only
  2397. * to length <b>cur_len</b> to decide a suitable middle hop for a
  2398. * circuit. In particular, make sure we don't pick the exit node or its
  2399. * family, and make sure we don't duplicate any previous nodes or their
  2400. * families. */
  2401. static const node_t *
  2402. choose_good_middle_server(uint8_t purpose,
  2403. cpath_build_state_t *state,
  2404. crypt_path_t *head,
  2405. int cur_len)
  2406. {
  2407. const node_t *choice;
  2408. smartlist_t *excluded;
  2409. const or_options_t *options = get_options();
  2410. router_crn_flags_t flags = CRN_NEED_DESC;
  2411. tor_assert(CIRCUIT_PURPOSE_MIN_ <= purpose &&
  2412. purpose <= CIRCUIT_PURPOSE_MAX_);
  2413. log_debug(LD_CIRC, "Contemplating intermediate hop #%d: random choice.",
  2414. cur_len+1);
  2415. excluded = build_middle_exclude_list(purpose, state, head, cur_len);
  2416. if (state->need_uptime)
  2417. flags |= CRN_NEED_UPTIME;
  2418. if (state->need_capacity)
  2419. flags |= CRN_NEED_CAPACITY;
  2420. /** If a hidden service circuit wants a specific middle node, pin it. */
  2421. if (middle_node_must_be_vanguard(options, purpose, cur_len)) {
  2422. log_debug(LD_GENERAL, "Picking a sticky node (cur_len = %d)", cur_len);
  2423. return pick_vanguard_middle_node(options, flags, cur_len, excluded);
  2424. }
  2425. choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
  2426. smartlist_free(excluded);
  2427. return choice;
  2428. }
  2429. /** Pick a good entry server for the circuit to be built according to
  2430. * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
  2431. * router (if we're an OR), and respect firewall settings; if we're
  2432. * configured to use entry guards, return one.
  2433. *
  2434. * Set *<b>guard_state_out</b> to information about the guard that
  2435. * we're selecting, which we'll use later to remember whether the
  2436. * guard worked or not.
  2437. */
  2438. const node_t *
  2439. choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state,
  2440. circuit_guard_state_t **guard_state_out)
  2441. {
  2442. const node_t *choice;
  2443. smartlist_t *excluded;
  2444. const or_options_t *options = get_options();
  2445. /* If possible, choose an entry server with a preferred address,
  2446. * otherwise, choose one with an allowed address */
  2447. router_crn_flags_t flags = (CRN_NEED_GUARD|CRN_NEED_DESC|CRN_PREF_ADDR|
  2448. CRN_DIRECT_CONN);
  2449. const node_t *node;
  2450. /* Once we used this function to select a node to be a guard. We had
  2451. * 'state == NULL' be the signal for that. But we don't do that any more.
  2452. */
  2453. tor_assert_nonfatal(state);
  2454. if (state && options->UseEntryGuards &&
  2455. (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) {
  2456. /* This request is for an entry server to use for a regular circuit,
  2457. * and we use entry guard nodes. Just return one of the guard nodes. */
  2458. tor_assert(guard_state_out);
  2459. return guards_choose_guard(state, guard_state_out);
  2460. }
  2461. excluded = smartlist_new();
  2462. if (state && (node = build_state_get_exit_node(state))) {
  2463. /* Exclude the exit node from the state, if we have one. Also exclude its
  2464. * family. */
  2465. nodelist_add_node_and_family(excluded, node);
  2466. }
  2467. if (state) {
  2468. if (state->need_uptime)
  2469. flags |= CRN_NEED_UPTIME;
  2470. if (state->need_capacity)
  2471. flags |= CRN_NEED_CAPACITY;
  2472. }
  2473. choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
  2474. smartlist_free(excluded);
  2475. return choice;
  2476. }
  2477. /** Return the first non-open hop in cpath, or return NULL if all
  2478. * hops are open. */
  2479. static crypt_path_t *
  2480. onion_next_hop_in_cpath(crypt_path_t *cpath)
  2481. {
  2482. crypt_path_t *hop = cpath;
  2483. do {
  2484. if (hop->state != CPATH_STATE_OPEN)
  2485. return hop;
  2486. hop = hop->next;
  2487. } while (hop != cpath);
  2488. return NULL;
  2489. }
  2490. /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
  2491. * based on <b>state</b>. Append the hop info to head_ptr.
  2492. *
  2493. * Return 1 if the path is complete, 0 if we successfully added a hop,
  2494. * and -1 on error.
  2495. */
  2496. static int
  2497. onion_extend_cpath(origin_circuit_t *circ)
  2498. {
  2499. uint8_t purpose = circ->base_.purpose;
  2500. cpath_build_state_t *state = circ->build_state;
  2501. int cur_len = circuit_get_cpath_len(circ);
  2502. extend_info_t *info = NULL;
  2503. if (cur_len >= state->desired_path_len) {
  2504. log_debug(LD_CIRC, "Path is complete: %d steps long",
  2505. state->desired_path_len);
  2506. return 1;
  2507. }
  2508. log_debug(LD_CIRC, "Path is %d long; we want %d", cur_len,
  2509. state->desired_path_len);
  2510. if (cur_len == state->desired_path_len - 1) { /* Picking last node */
  2511. info = extend_info_dup(state->chosen_exit);
  2512. } else if (cur_len == 0) { /* picking first node */
  2513. const node_t *r = choose_good_entry_server(purpose, state,
  2514. &circ->guard_state);
  2515. if (r) {
  2516. /* If we're a client, use the preferred address rather than the
  2517. primary address, for potentially connecting to an IPv6 OR
  2518. port. Servers always want the primary (IPv4) address. */
  2519. int client = (server_mode(get_options()) == 0);
  2520. info = extend_info_from_node(r, client);
  2521. /* Clients can fail to find an allowed address */
  2522. tor_assert_nonfatal(info || client);
  2523. }
  2524. } else {
  2525. const node_t *r =
  2526. choose_good_middle_server(purpose, state, circ->cpath, cur_len);
  2527. if (r) {
  2528. info = extend_info_from_node(r, 0);
  2529. tor_assert_nonfatal(info);
  2530. }
  2531. }
  2532. if (!info) {
  2533. log_warn(LD_CIRC,"Failed to find node for hop #%d of our path. Discarding "
  2534. "this circuit.", cur_len+1);
  2535. return -1;
  2536. }
  2537. log_debug(LD_CIRC,"Chose router %s for hop #%d (exit is %s)",
  2538. extend_info_describe(info),
  2539. cur_len+1, build_state_get_exit_nickname(state));
  2540. onion_append_hop(&circ->cpath, info);
  2541. extend_info_free(info);
  2542. return 0;
  2543. }
  2544. /** Create a new hop, annotate it with information about its
  2545. * corresponding router <b>choice</b>, and append it to the
  2546. * end of the cpath <b>head_ptr</b>. */
  2547. STATIC int
  2548. onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
  2549. {
  2550. crypt_path_t *hop = tor_malloc_zero(sizeof(crypt_path_t));
  2551. /* link hop into the cpath, at the end. */
  2552. onion_append_to_cpath(head_ptr, hop);
  2553. hop->magic = CRYPT_PATH_MAGIC;
  2554. hop->state = CPATH_STATE_CLOSED;
  2555. hop->extend_info = extend_info_dup(choice);
  2556. hop->package_window = circuit_initial_package_window();
  2557. hop->deliver_window = CIRCWINDOW_START;
  2558. return 0;
  2559. }
  2560. /** Allocate a new extend_info object based on the various arguments. */
  2561. extend_info_t *
  2562. extend_info_new(const char *nickname,
  2563. const char *rsa_id_digest,
  2564. const ed25519_public_key_t *ed_id,
  2565. crypto_pk_t *onion_key,
  2566. const curve25519_public_key_t *ntor_key,
  2567. const tor_addr_t *addr, uint16_t port)
  2568. {
  2569. extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
  2570. memcpy(info->identity_digest, rsa_id_digest, DIGEST_LEN);
  2571. if (ed_id && !ed25519_public_key_is_zero(ed_id))
  2572. memcpy(&info->ed_identity, ed_id, sizeof(ed25519_public_key_t));
  2573. if (nickname)
  2574. strlcpy(info->nickname, nickname, sizeof(info->nickname));
  2575. if (onion_key)
  2576. info->onion_key = crypto_pk_dup_key(onion_key);
  2577. if (ntor_key)
  2578. memcpy(&info->curve25519_onion_key, ntor_key,
  2579. sizeof(curve25519_public_key_t));
  2580. tor_addr_copy(&info->addr, addr);
  2581. info->port = port;
  2582. return info;
  2583. }
  2584. /** Allocate and return a new extend_info that can be used to build a
  2585. * circuit to or through the node <b>node</b>. Use the primary address
  2586. * of the node (i.e. its IPv4 address) unless
  2587. * <b>for_direct_connect</b> is true, in which case the preferred
  2588. * address is used instead. May return NULL if there is not enough
  2589. * info about <b>node</b> to extend to it--for example, if there is no
  2590. * routerinfo_t or microdesc_t, or if for_direct_connect is true and none of
  2591. * the node's addresses are allowed by tor's firewall and IP version config.
  2592. **/
  2593. extend_info_t *
  2594. extend_info_from_node(const node_t *node, int for_direct_connect)
  2595. {
  2596. tor_addr_port_t ap;
  2597. int valid_addr = 0;
  2598. if (node->ri == NULL && (node->rs == NULL || node->md == NULL))
  2599. return NULL;
  2600. /* Choose a preferred address first, but fall back to an allowed address.
  2601. * choose_address returns 1 on success, but get_prim_orport returns 0. */
  2602. if (for_direct_connect)
  2603. valid_addr = fascist_firewall_choose_address_node(node,
  2604. FIREWALL_OR_CONNECTION,
  2605. 0, &ap);
  2606. else
  2607. valid_addr = !node_get_prim_orport(node, &ap);
  2608. if (valid_addr)
  2609. log_debug(LD_CIRC, "using %s for %s",
  2610. fmt_addrport(&ap.addr, ap.port),
  2611. node->ri ? node->ri->nickname : node->rs->nickname);
  2612. else
  2613. log_warn(LD_CIRC, "Could not choose valid address for %s",
  2614. node->ri ? node->ri->nickname : node->rs->nickname);
  2615. /* Every node we connect or extend to must support ntor */
  2616. if (!node_has_curve25519_onion_key(node)) {
  2617. log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
  2618. "Attempted to create extend_info for a node that does not support "
  2619. "ntor: %s", node_describe(node));
  2620. return NULL;
  2621. }
  2622. const ed25519_public_key_t *ed_pubkey = NULL;
  2623. /* Don't send the ed25519 pubkey unless the target node actually supports
  2624. * authenticating with it. */
  2625. if (node_supports_ed25519_link_authentication(node, 0)) {
  2626. log_info(LD_CIRC, "Including Ed25519 ID for %s", node_describe(node));
  2627. ed_pubkey = node_get_ed25519_id(node);
  2628. } else if (node_get_ed25519_id(node)) {
  2629. log_info(LD_CIRC, "Not including the ed25519 ID for %s, since it won't "
  2630. "be able to authenticate it.",
  2631. node_describe(node));
  2632. }
  2633. /* Retrieve the curve25519 pubkey. */
  2634. const curve25519_public_key_t *curve_pubkey =
  2635. node_get_curve25519_onion_key(node);
  2636. if (valid_addr && node->ri)
  2637. return extend_info_new(node->ri->nickname,
  2638. node->identity,
  2639. ed_pubkey,
  2640. node->ri->onion_pkey,
  2641. curve_pubkey,
  2642. &ap.addr,
  2643. ap.port);
  2644. else if (valid_addr && node->rs && node->md)
  2645. return extend_info_new(node->rs->nickname,
  2646. node->identity,
  2647. ed_pubkey,
  2648. node->md->onion_pkey,
  2649. curve_pubkey,
  2650. &ap.addr,
  2651. ap.port);
  2652. else
  2653. return NULL;
  2654. }
  2655. /** Release storage held by an extend_info_t struct. */
  2656. void
  2657. extend_info_free_(extend_info_t *info)
  2658. {
  2659. if (!info)
  2660. return;
  2661. crypto_pk_free(info->onion_key);
  2662. tor_free(info);
  2663. }
  2664. /** Allocate and return a new extend_info_t with the same contents as
  2665. * <b>info</b>. */
  2666. extend_info_t *
  2667. extend_info_dup(extend_info_t *info)
  2668. {
  2669. extend_info_t *newinfo;
  2670. tor_assert(info);
  2671. newinfo = tor_malloc(sizeof(extend_info_t));
  2672. memcpy(newinfo, info, sizeof(extend_info_t));
  2673. if (info->onion_key)
  2674. newinfo->onion_key = crypto_pk_dup_key(info->onion_key);
  2675. else
  2676. newinfo->onion_key = NULL;
  2677. return newinfo;
  2678. }
  2679. /** Return the node_t for the chosen exit router in <b>state</b>.
  2680. * If there is no chosen exit, or if we don't know the node_t for
  2681. * the chosen exit, return NULL.
  2682. */
  2683. const node_t *
  2684. build_state_get_exit_node(cpath_build_state_t *state)
  2685. {
  2686. if (!state || !state->chosen_exit)
  2687. return NULL;
  2688. return node_get_by_id(state->chosen_exit->identity_digest);
  2689. }
  2690. /** Return the RSA ID digest for the chosen exit router in <b>state</b>.
  2691. * If there is no chosen exit, return NULL.
  2692. */
  2693. const uint8_t *
  2694. build_state_get_exit_rsa_id(cpath_build_state_t *state)
  2695. {
  2696. if (!state || !state->chosen_exit)
  2697. return NULL;
  2698. return (const uint8_t *) state->chosen_exit->identity_digest;
  2699. }
  2700. /** Return the nickname for the chosen exit router in <b>state</b>. If
  2701. * there is no chosen exit, or if we don't know the routerinfo_t for the
  2702. * chosen exit, return NULL.
  2703. */
  2704. const char *
  2705. build_state_get_exit_nickname(cpath_build_state_t *state)
  2706. {
  2707. if (!state || !state->chosen_exit)
  2708. return NULL;
  2709. return state->chosen_exit->nickname;
  2710. }
  2711. /** Return true iff the given address can be used to extend to. */
  2712. int
  2713. extend_info_addr_is_allowed(const tor_addr_t *addr)
  2714. {
  2715. tor_assert(addr);
  2716. /* Check if we have a private address and if we can extend to it. */
  2717. if ((tor_addr_is_internal(addr, 0) || tor_addr_is_multicast(addr)) &&
  2718. !get_options()->ExtendAllowPrivateAddresses) {
  2719. goto disallow;
  2720. }
  2721. /* Allowed! */
  2722. return 1;
  2723. disallow:
  2724. return 0;
  2725. }
  2726. /* Does ei have a valid TAP key? */
  2727. int
  2728. extend_info_supports_tap(const extend_info_t* ei)
  2729. {
  2730. tor_assert(ei);
  2731. /* Valid TAP keys are not NULL */
  2732. return ei->onion_key != NULL;
  2733. }
  2734. /* Does ei have a valid ntor key? */
  2735. int
  2736. extend_info_supports_ntor(const extend_info_t* ei)
  2737. {
  2738. tor_assert(ei);
  2739. /* Valid ntor keys have at least one non-zero byte */
  2740. return !tor_mem_is_zero(
  2741. (const char*)ei->curve25519_onion_key.public_key,
  2742. CURVE25519_PUBKEY_LEN);
  2743. }
  2744. /* Is circuit purpose allowed to use the deprecated TAP encryption protocol?
  2745. * The hidden service protocol still uses TAP for some connections, because
  2746. * ntor onion keys aren't included in HS descriptors or INTRODUCE cells. */
  2747. static int
  2748. circuit_purpose_can_use_tap_impl(uint8_t purpose)
  2749. {
  2750. return (purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
  2751. purpose == CIRCUIT_PURPOSE_C_INTRODUCING);
  2752. }
  2753. /* Is circ allowed to use the deprecated TAP encryption protocol?
  2754. * The hidden service protocol still uses TAP for some connections, because
  2755. * ntor onion keys aren't included in HS descriptors or INTRODUCE cells. */
  2756. int
  2757. circuit_can_use_tap(const origin_circuit_t *circ)
  2758. {
  2759. tor_assert(circ);
  2760. tor_assert(circ->cpath);
  2761. tor_assert(circ->cpath->extend_info);
  2762. return (circuit_purpose_can_use_tap_impl(circ->base_.purpose) &&
  2763. extend_info_supports_tap(circ->cpath->extend_info));
  2764. }
  2765. /* Does circ have an onion key which it's allowed to use? */
  2766. int
  2767. circuit_has_usable_onion_key(const origin_circuit_t *circ)
  2768. {
  2769. tor_assert(circ);
  2770. tor_assert(circ->cpath);
  2771. tor_assert(circ->cpath->extend_info);
  2772. return (extend_info_supports_ntor(circ->cpath->extend_info) ||
  2773. circuit_can_use_tap(circ));
  2774. }
  2775. /* Does ei have an onion key which it would prefer to use?
  2776. * Currently, we prefer ntor keys*/
  2777. int
  2778. extend_info_has_preferred_onion_key(const extend_info_t* ei)
  2779. {
  2780. tor_assert(ei);
  2781. return extend_info_supports_ntor(ei);
  2782. }
  2783. /** Find the circuits that are waiting to find out whether their guards are
  2784. * usable, and if any are ready to become usable, mark them open and try
  2785. * attaching streams as appropriate. */
  2786. void
  2787. circuit_upgrade_circuits_from_guard_wait(void)
  2788. {
  2789. smartlist_t *to_upgrade =
  2790. circuit_find_circuits_to_upgrade_from_guard_wait();
  2791. if (to_upgrade == NULL)
  2792. return;
  2793. log_info(LD_GUARD, "Upgrading %d circuits from 'waiting for better guard' "
  2794. "to 'open'.", smartlist_len(to_upgrade));
  2795. SMARTLIST_FOREACH_BEGIN(to_upgrade, origin_circuit_t *, circ) {
  2796. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  2797. circuit_has_opened(circ);
  2798. } SMARTLIST_FOREACH_END(circ);
  2799. smartlist_free(to_upgrade);
  2800. }