This is a Gemara in Nidda (19) as well as other places. Rashi adds on קבלה מרבו הלכה למשה מסיני, that he needs to have a tradition from his Rebbe going back to Moshe Rabenu.
However, this principle doesn't stand up. The Gemara in many places has a dispute about a gezera shava, one Tanna learns a gezera shava and one doesn't. How can that be if every gezera shava comes as a tradition from Moshe? The Gemara states in some places that Tanna A had one gezera shava and Tanna B had a different gezera shava and neither one accepted the others gezera shava. Does that make any sense if every gezera shava is from Moshe? It gets worse. The Gemara in Nidda (22) states rules about gezera shavas. The Gemara says that if it is מופנה מצד אחד למידיון ומשיבין and if מופנה משני צדדים למידין ואין משיבים. The obvious question (asked by Rishonim and Acharonim) is these rules make no sense. If there is a tradition about a gezera shava (going back to Moshe) then everyone should accept it no matter what and if there is no tradition no should accept even if it is מופנה משני צדדים. The Rishonim and Acharonim give various difficult answers:
1. The Ramban in the second shoresh on the Sefer Hamitzvos explains based on the questions above that we can't accept the simple explanation of gezera shava. Rather he says the following. The Rabbis had a tradition that there was a gezera shava with a given pair of words (e.g. שחט שחט) but didn't know which iteration of the word in the Torah is part of the gezera shava. Therefore there are disputes about gezera shavas.
The difficulty is obvious. The Gemara enunciates a clear principle and the Rishonim emasculate the principle so that it is basically meaningless.
2. Tosafos Shabbos 97a states that the Rabbis knew that there were a certain number of gezera shavas and therefore they couldn't just accept every gezera shava from every Rabbi because they had to make sure that they had the right number of gezera shavas. The weakness and difficulty of this answer is obvious.
- Why didn't chazal tell us this number anywhere? Chazal tell us how many mitzvos there are how many melachos, etc. but this critical point is left out.
- If all Moshe got was the number of Gezera Shavas then אין אדם דן גזירה שווה מעצמו doesn't make any sense, every gezera shava is מעצמו
3. The הליכות עולם gives a similar answer to the Ramban but he states that sometimes they got more information then other times. Some gezera shavas had the words and the halacha and the place. Some had just the words, some had the words and the halacha.
The bottom line is that the Gemara enunciates a very broad strong principle, however, in parctice this is contradicted all over the place and the Rishonim/Acharonim need to give weak farfetched answers. What we see is that the mesora even on something as simple as gezera shavas is non-existent.